Paper detail

On Weighted Multicommodity Flows in Directed Networks

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 $μ\colon S \times S \to \R_+$, the \emph{$μ$-value} of $F$ is $\sum_P F(P) μ(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 $μ$-value multiflow problem has an integer optimal solution when $μ$ 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.