Disjoint paths in graphs

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)979-991
Number of pages13
JournalDiscrete Mathematics
Volume306
Issue number10-11
DOIs
StatePublished - May 28 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Disjoint paths in graphs'. Together they form a unique fingerprint.

Cite this