On Weighted Multicommodity Flows in Directed Networks

Abstract

Let $G=(VG,AG)$ be a directed graph with a set $S\subseteq VG$ of terminals and nonnegative integer arc capacities $c$. A feasible multiflow is a nonnegative real function $F(P)$ of "flows" on paths $P$ connecting distinct terminals such that the sum of flows through each arc $a$ does not exceed $c(a)$. Given $\mu :S\times S\to {\mathbb{R}}_{+}$, the \emph{$\mu$-value} of $F$ is ${\sum }_{P}F(P)\mu (s_P,t_P)$, where $s_P$ and $t_P$ are the start and end vertices of a path $P$, respectively. Using a sophisticated topological approach, Hirai and Koichi showed that the maximum $\mu$-value multiflow problem has an integer optimal solution when $\mu$ is the distance generated by subtrees of a weighted directed tree and $(G,S,c)$ satisfies certain Eulerian conditions. We give a combinatorial proof of that result and devise a strongly polynomial combinatorial algorithm.

12 pages

Cited by in corpus (1)

• A compact representation for minimizers of $k$-submodular functions