Disjoint paths in graphs

P. D. Seymour

doi:10.1016/j.disc.2006.03.019

Disjoint paths in graphs

P. D. Seymour

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

Suppose that (s₁, t₁), ..., (s_k, t_k) are pairs of vertices of a graph. When can one choose a path between s_i and t_i for each i, all pairwise edge-disjoint? Menger's theorem answers this when s₁, ..., s_k, t₁, ..., t_k take only two distinct values, but the general problem is unsolved. We settle the two next simplest cases,. (i) when k = 2, and. (ii) when s₁, ..., s_k, t₁, ..., t_k take only three distinct values-the solution to this is obtained by applying a theorem of Mader. We obtain both good characterizations and good algorithms for these problems. The analogous "vertex-disjoint" problems are also solved.

Original language	English (US)
Pages (from-to)	979-991
Number of pages	13
Journal	Discrete Mathematics
Volume	306
Issue number	10-11
DOIs	https://doi.org/10.1016/j.disc.2006.03.019
State	Published - May 28 2006
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2006.03.019

Cite this

@article{c7f375e88df84e3ebe4e7596f5b1456b,

title = "Disjoint paths in graphs",

abstract = "Suppose that (s1, t1), ..., (sk, tk) are pairs of vertices of a graph. When can one choose a path between si and ti for each i, all pairwise edge-disjoint? Menger's theorem answers this when s1, ..., sk, t1, ..., tk take only two distinct values, but the general problem is unsolved. We settle the two next simplest cases,. (i) when k = 2, and. (ii) when s1, ..., sk, t1, ..., tk take only three distinct values-the solution to this is obtained by applying a theorem of Mader. We obtain both good characterizations and good algorithms for these problems. The analogous {"}vertex-disjoint{"} problems are also solved.",

author = "Seymour, \{P. D.\}",

year = "2006",

month = may,

day = "28",

doi = "10.1016/j.disc.2006.03.019",

language = "English (US)",

volume = "306",

pages = "979--991",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "10-11",

}

TY - JOUR

T1 - Disjoint paths in graphs

AU - Seymour, P. D.

PY - 2006/5/28

Y1 - 2006/5/28

N2 - Suppose that (s1, t1), ..., (sk, tk) are pairs of vertices of a graph. When can one choose a path between si and ti for each i, all pairwise edge-disjoint? Menger's theorem answers this when s1, ..., sk, t1, ..., tk take only two distinct values, but the general problem is unsolved. We settle the two next simplest cases,. (i) when k = 2, and. (ii) when s1, ..., sk, t1, ..., tk take only three distinct values-the solution to this is obtained by applying a theorem of Mader. We obtain both good characterizations and good algorithms for these problems. The analogous "vertex-disjoint" problems are also solved.

AB - Suppose that (s1, t1), ..., (sk, tk) are pairs of vertices of a graph. When can one choose a path between si and ti for each i, all pairwise edge-disjoint? Menger's theorem answers this when s1, ..., sk, t1, ..., tk take only two distinct values, but the general problem is unsolved. We settle the two next simplest cases,. (i) when k = 2, and. (ii) when s1, ..., sk, t1, ..., tk take only three distinct values-the solution to this is obtained by applying a theorem of Mader. We obtain both good characterizations and good algorithms for these problems. The analogous "vertex-disjoint" problems are also solved.

UR - https://www.scopus.com/pages/publications/33744507048

UR - https://www.scopus.com/inward/citedby.url?scp=33744507048&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2006.03.019

DO - 10.1016/j.disc.2006.03.019

M3 - Article

AN - SCOPUS:33744507048

SN - 0012-365X

VL - 306

SP - 979

EP - 991

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 10-11

ER -

Disjoint paths in graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this