|
Вестник Московского университета. Серия 1: Математика. Механика, 2006, номер 2, страницы 52–54
(Mi vmumm1122)
|
|
|
|
Краткие сообщения
Быстрый алгоритм построения декомпозиции многополюсных потоков
М. А. Бабенко
Аннотация:
В работе предложен алгоритм, позволяющий по заданному в сети $G=(V,E)$ $S$-$T$-потоку
$f\colon E\to\mathbb{R}_+=$ построить его разложение в сумму $S\times T$ потоков между всевозможными
парами истоков и стоков за время $O(|E|(2+\log(|V|^2/|E|)))$ (считая мощности множеств $S$ и $T$
фиксированными). Эти потоки будут целочисленными, если
таковым был исходный поток $f$.
Библиогр. 2.
Поступила в редакцию: 05.05.2005
Образец цитирования:
М. А. Бабенко, “Быстрый алгоритм построения декомпозиции многополюсных потоков”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2006, № 2, 52–54
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmumm1122 https://www.mathnet.ru/rus/vmumm/y2006/i2/p52
|
Статистика просмотров: |
Страница аннотации: | 49 | PDF полного текста: | 27 |
|