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.
