The multiroute maximum flow problem revisited
Donglei Du, R. Chandrasekaran · Networks · 2005
Abstract We are given a directed network G = (V,A,u) with vertex set V, arc set A, a source vertex s ∈ V, a destination vertex t ∈ V, a finite capacity vector u = {uij}(i,j)∈A, and a positive integer m ∈ Z+. The multiroute maximum flow problem (m‐MFP) generalizes the ordinary maximum flow problem by seeking a maximum flow from s to t subject to not only the regular flow conservation constraints at the vertices (except s and t) and the flow capacity constraints at the arcs, but also the extra constraints that any flow must be routed along m arc‐disjoint s‐t paths. In this article, we devise two new combinatorial algorithms for m‐MFP. One is based on Newton's method and another is based on an augmenting‐path technique. We also show how the Newton‐based algorithm unifies two existing algorithms, and how the augmenting‐path algorithm is strongly polynomial for case m = 2. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(2), 81–92 2006