|
Проблемы передачи информации, 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
Образец цитирования:
М. А. Бабенко, “О потоках в простых двунаправленных и кососимметрических сетях”, Пробл. передачи информ., 42:4 (2006), 104–120; Problems Inform. Transmission, 42:4 (2006), 356–370
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ppi65 https://www.mathnet.ru/rus/ppi/v42/i4/p104
|
Статистика просмотров: |
Страница аннотации: | 427 | PDF полного текста: | 438 | Список литературы: | 49 | Первая страница: | 1 |
|