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

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