Проблемы передачи информации
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Пробл. передачи информ.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Проблемы передачи информации, 2006, том 42, выпуск 4, страницы 104–120 (Mi ppi65)  

Теория сетей связи

О потоках в простых двунаправленных и кососимметрических сетях

М. А. Бабенко

Московский государственный университет им. М. В. Ломоносова, механико-математический факультет
Список литературы:
Аннотация: Пусть задана простая направленная сеть. Результаты Карзанова, Эвена и Таржана показывают, что метод блокирующего потока позволяет построить в ней максимальный целочисленный поток за время $O(m\min(m^{1/2},n^{2/3}))$ (здесь и далее $n$ – число вершин, $m$ – число дуг).
Если данная сеть является простой двунаправленной, то сведение, предложенное Габовым, позволяет решать задачу о максимальном целочисленном потоке в ней за время $O(m^{3/2})$. В статье показано, что эта задача разрешима также и за время $O(mn^{2/3})$ с помощью варианта метода блокирующего потока, тем самым полностью ликвидирован зазор между сложностями направленного и двунаправленного вариантов.
Результаты изложены в эквивалентных терминах кососимметрических сетей. Для получения требуемой оценки $O(mn^{2/3})$ доказывается, что величина целочисленного $s$$s'$ потока в кососимметрической сети без кратных дуг не превосходит $O(Un^2/d^2)$, где $d$ – длина кратчайшего регулярного $s$$s'$ пути в расщепленной сети, a $U$ – максимальная пропускная способность. Мы также устанавливаем, что если поток величины $v$ в кососимметрической сети без кратных дуг является ациклическим, то он принимает ненулевые значения лишь на $O(n\sqrt v)$ дугах.
Поступила в редакцию: 01.06.2006
После переработки: 08.08.2006
Англоязычная версия:
Problems of Information Transmission, 2006, Volume 42, Issue 4, Pages 356–370
DOI: https://doi.org/10.1134/S0032946006040089
Реферативные базы данных:
Тип публикации: Статья
УДК: 621.394.74:519.2
Образец цитирования: М. А. Бабенко, “О потоках в простых двунаправленных и кососимметрических сетях”, Пробл. передачи информ., 42:4 (2006), 104–120; Problems Inform. Transmission, 42:4 (2006), 356–370
Цитирование в формате AMSBIB
\RBibitem{Bab06}
\by М.~А.~Бабенко
\paper О~потоках в~простых двунаправленных и кососимметрических сетях
\jour Пробл. передачи информ.
\yr 2006
\vol 42
\issue 4
\pages 104--120
\mathnet{http://mi.mathnet.ru/ppi65}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2278815}
\transl
\jour Problems Inform. Transmission
\yr 2006
\vol 42
\issue 4
\pages 356--370
\crossref{https://doi.org/10.1134/S0032946006040089}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33846839453}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/ppi65
  • https://www.mathnet.ru/rus/ppi/v42/i4/p104
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Проблемы передачи информации Problems of Information Transmission
    Статистика просмотров:
    Страница аннотации:427
    PDF полного текста:438
    Список литературы:49
    Первая страница:1
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024