• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Min-Cost Multiflows in Node-Capacitated Undirected Networks

Journal of Combinatorial Optimization. 2012. Vol. 24. No. 3. P. 202-228.
Babenko M. A., Karzanov A. V.

Рассмотрим неориентированный граф $G = (VG, EG)$, в котором выделено множество терминалов $T \subseteq VG$, и заданы неотрицательные пропускные способности $c(v)$, а также стоимости $a(v)$ для всех вершин $v\in VG$. Путь в $G$ называется $T$-путем, если его концы представляют собой различные терминалы. Мультипотоком называется функция $F$, приписывающую каждому $T$-пути $P$ неотрицательный рациональный вес $F(P)$. Мультипоток называется допустимым, если сумма весов $T$-путей, проходящих через каждую вершину $v$, не превышает $c(v)$. Величиной $F$ называется сумма весов $F(P)$, а стоимостью $F$ называется сумма  (по всем $T$-путям $P$) произведений $F(P)$ на стоимости путей $P$ относительно функции $a$. В данной работе мы обобщаем известные результаты, касающиеся мультипотоков с ограничениями пропускных способностей на ребрах, и доказываем, что задача нахождения мультипотока минимальной стоимости среди мультипотоков, имеющих максимальную величину всегда имеет полуцелое прямое и двойственное решения. Более того, мы описываем сильнополиномиальный алгоритм, строящий такие решения.