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

J.C.M. Keijsper; R.A. Pendavingh; L. Stougie

doi:10.1016/j.jctb.2005.07.002

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

J.C.M. Keijsper, R.A. Pendavingh, L. Stougie

Research output: Contribution to Journal › Article › Academic › peer-review

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 language	English
Pages (from-to)	159-163
Journal	Journal of Combinatorial Theory, Series B
Volume	96
Issue number	1
DOIs	https://doi.org/10.1016/j.jctb.2005.07.002
Publication status	Published - 2006

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1016/j.jctb.2005.07.002

Persistent URL (handle)

Persistent link

Cite this

@article{e6de0e8f2b4f4294a284306cb5c4c283,

title = "A linear programming formulation of Mader's edge-disjoint paths problem",

abstract = "We give a dual pair of linear programs for a min{\^a}€“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",

author = "J.C.M. Keijsper and R.A. Pendavingh and L. Stougie",

year = "2006",

doi = "10.1016/j.jctb.2005.07.002",

language = "English",

volume = "96",

pages = "159--163",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

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

AU - Keijsper, J.C.M.

AU - Pendavingh, R.A.

AU - Stougie, L.

PY - 2006

Y1 - 2006

N2 - 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

AB - 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

U2 - 10.1016/j.jctb.2005.07.002

DO - 10.1016/j.jctb.2005.07.002

M3 - Article

SN - 0095-8956

VL - 96

SP - 159

EP - 163

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 1

ER -

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

Abstract

UN SDGs

Access to Document

Persistent URL (handle)

Fingerprint

Cite this