A linear programming formulation of Mader's edge-disjoint paths problem (Q2581506): Difference between revisions

Suppose we have a graph with for each edge a capacity, and a specified subset \(T\) of the vertices. The paper looks at the problem of finding a maximum number of disjoint paths between vertices in \(T\) such for each edge \(e\), its capacity is an upper bound on the number of paths that use \(e\). The paper shows that this problem can be solved in polynomial time with an algorithm, based on the ellipsoid method: this is done by giving a dual pair of linear programs for a min-max result of Mader for the number of edge disjoint paths between vertices in \(T\).