Graph minors .XIII. The disjoint paths problem

Neil Robertson, P. D. Seymour

Research output: Contribution to journalArticlepeer-review

932 Scopus citations

Abstract

We describe an algorithm, which for fixed k ≥ 0 has running time O(|V(G)|3), to solve the following problem: given a graph G and k pairs of vertices of G, decide if there are k mutually vertex-disjoint paths of G joining the pairs.

Original languageEnglish (US)
Pages (from-to)65-110
Number of pages46
JournalJournal of Combinatorial Theory, Series B
Volume63
Issue number1
DOIs
StatePublished - Jan 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Graph minors .XIII. The disjoint paths problem'. Together they form a unique fingerprint.

Cite this