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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

9 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	159-163
Tijdschrift	Journal of Combinatorial Theory, Series B
Volume	96
Nummer van het tijdschrift	1
DOI's	https://doi.org/10.1016/j.jctb.2005.07.002
Status	Gepubliceerd - 2006

Toegang tot document

10.1016/j.jctb.2005.07.002

Citeer dit

@article{b2fa89c7fa954cb39f93cd62e46aa622,

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

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.",

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

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit