?
Min-Cost Multiflows in Node-Capacitated Undirected Networks
Рассмотрим неориентированный граф $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$. В данной работе мы обобщаем известные результаты, касающиеся мультипотоков с ограничениями пропускных способностей на ребрах, и доказываем, что задача нахождения мультипотока минимальной стоимости среди мультипотоков, имеющих максимальную величину всегда имеет полуцелое прямое и двойственное решения. Более того, мы описываем сильнополиномиальный алгоритм, строящий такие решения.