On the complexity of the disjoint paths problem

DOI10.1007/BF01202792zbMath0770.68072OpenAlexW2041884875MaRDI QIDQ2367446

Frank Pfeiffer, Matthias Middendorf

Publication date: 16 August 1993

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01202792

zbMATH Keywords

NP-completenessvertex disjoint pathshalf- integral relaxationplanar edge-disjoint paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45)

Related Items

Edge routing with ordered bundles ⋮ Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation ⋮ Towards Single Face Shortest Vertex-Disjoint Paths in Undirected Planar Graphs ⋮ NP-completeness of some edge-disjoint paths problems ⋮ On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary ⋮ Irrelevant vertices for the planar disjoint paths problem ⋮ The complexity of planar graph choosability ⋮ On the maximum degree of path-pairable planar graphs ⋮ The disjoint shortest paths problem ⋮ Combing a Linkage in an Annulus ⋮ Solving the edge‐disjoint paths problem using a two‐stage method ⋮ On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ The disjoint paths problem in quadratic time ⋮ Approximating maximum integral multiflows on bounded genus graphs ⋮ Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs ⋮ Multiflow Feasibility: An Annotated Tableau ⋮ Criticality for multicommodity flows ⋮ Orientations of graphs with prescribed weighted out-degrees ⋮ A polynomial-time algorithm for detecting the possibility of Braess paradox in directed graphs ⋮ Finding edge-disjoint paths in networks: an ant colony optimization algorithm ⋮ An Excluded Minor Characterization of Seymour Graphs ⋮ Tight Bounds for Linkages in Planar Graphs ⋮ Tight integral duality gap in the Chinese postman problem ⋮ The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs ⋮ Disjoint paths in sparse graphs ⋮ The complexity of path coloring and call scheduling ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Precoloring extension on unit interval graphs ⋮ Multiflows in symmetric digraphs ⋮ Max-multiflow/min-multicut for G+H series-parallel ⋮ Unnamed Item ⋮ Vertex disjoint paths on clique-width bounded graphs ⋮ The edge-disjoint paths problem is NP-complete for series-parallel graphs ⋮ The indefinite period traveling salesman problem ⋮ Disjoint paths in symmetric digraphs ⋮ Approximations for the disjoint paths problem in high-diameter planar networks ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs ⋮ Integer plane multiflow maximisation: one-quarter-approximation and gaps ⋮ On the complexity of the planar directed edge-disjoint paths problem ⋮ Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs

Cites Work

• Graph minors. III. Planar tree-width
• Combinatorial approaches to multiflow problems
• Matroids and multicommodity flows
• On Odd Cuts and Plane Multicommodity Flows
• Planar Formulae and Their Uses