Disjoint Paths—A Survey

DOI10.1137/0606030zbMath0565.05045OpenAlexW1996419691MaRDI QIDQ3679228

Neil Robertson, P. D. Seymour

Publication date: 1985

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0606030

zbMATH Keywords

vertex-disjoint paths

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Paths and cycles (05C38)

Related Items (19)

Faster 2-Disjoint-Shortest-Paths Algorithm ⋮ Searching forK_3,3in linear time ⋮ Fixed-Parameter Tractability, A Prehistory, ⋮ Nonconstructive advances in polynomial-time complexity ⋮ Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ The existence of homeomorphic subgraphs in chordal graphs ⋮ Polynomial-time self-reducibility: theoretical motivations and practical results^∗ ⋮ The disjoint shortest paths problem ⋮ Forbidden minors characterization of partial 3-trees ⋮ The theory of guaranteed search on graphs ⋮ Graphs with no 7-wheel subdivision ⋮ Constructive complexity ⋮ The vertex separation number of a graph equals its path-width ⋮ General vertex disjoint paths in series-parallel graphs ⋮ On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs ⋮ Structure and recognition of graphs with no 6-wheel subdivision ⋮ Algorithms and obstructions for linear-width and related search parameters ⋮ Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover ⋮ The structure of the models of decidable monadic theories of graphs

Cites Work

• Graph minors. VI. Disjoint paths across a disc
• Graph minors. V. Excluding a planar graph
• Graph minors. VII: Disjoint paths on a surface
• The directed subgraph homeomorphism problem
• Disjoint paths in graphs
• Graph minors. IV: Tree-width and well-quasi-ordering
• Graph minors. II. Algorithmic aspects of tree-width
• A Polynomial Solution to the Undirected Two Paths Problem
• On the Computational Complexity of Combinatorial Problems
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs

This page was built for publication: Disjoint Paths—A Survey