RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 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.

УДК: 519.852.35

Поступила в редакцию: 05.05.2005



Реферативные базы данных:


© МИАН, 2024