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

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)

Abstract

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 TV. 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.
Original languageEnglish
Pages (from-to)159-163
JournalJournal of Combinatorial Theory, Series B
Volume96
Issue number1
DOIs
Publication statusPublished - 2006

Fingerprint Dive into the research topics of 'A linear programming formulation of Mader's edge-disjoint paths problem'. Together they form a unique fingerprint.

Cite this