A linear programming formulation of Mader's edge-disjoint paths problem

摘要

We give a dual pair of linear programs for a min-max result of Mader describing the maximum number of edge-disjoint T-paths in a graph G = (V, E) with T C V. We conclude that there exists a polynomial-time algorithm (based on the ellipsoid method) for finding the maximum number of T-paths in a capacitated graph, where the number of T-paths using an edge does not exceed the capacity of that edge. (c) 2005 Elsevier Inc. All rights reserved.