On the complexity of the disjoint paths problem

DOI10.1007/BF01202792MaRDI QIDQ2367446zbMATH OpenOpenAlexFDO

Authors Matthias Middendorf, Frank Pfeiffer

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

half- integral relaxationNP-completenessplanar edge-disjoint pathsvertex disjoint paths

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 47435
• scientific article; zbMATH DE number 4191702
• On the disjoint paths problem
• On the complexity of vertex-disjoint length-restricted path problems
• Finding disjoint paths with different path-costs: Complexity and algorithms
• On the complexity of the planar directed edge-disjoint paths problem
• The disjoint paths problem in quadratic time
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
• NP-completeness of some edge-disjoint paths problems

Cites work

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

Cited in

(84)

• Disjoint paths in symmetric digraphs
• Edge-disjoint paths in planar graphs
• The complexity of planar graph choosability
• Parallel complexity of computing a maximal set of disjoint paths
• Tight integral duality gap in the Chinese postman problem
• General vertex disjoint paths in series-parallel graphs
• Approximations for the disjoint paths problem in high-diameter planar networks
• The disjoint shortest paths problem
• Complexity of path discovery game problems
• A polynomial-time algorithm for detecting the possibility of Braess paradox in directed graphs
• On the complexity of vertex-disjoint length-restricted path problems
• Eulerian disjoint paths problem in grid graphs is NP-complete
• NP-completeness of some edge-disjoint paths problems
• A note on packing paths in planar graphs
• Integer plane multiflow maximisation: one-quarter-approximation and gaps
• On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary
• On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms
• Max-multiflow/min-multicut for G+H series-parallel
• On the maximum degree of path-pairable planar graphs
• Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
• Complexity of the path avoiding forbidden pairs problem revisited
• Finding edge-disjoint paths in networks: an ant colony optimization algorithm
• Precoloring extension on unit interval graphs
• Vertex disjoint paths on clique-width bounded graphs
• Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs
• On the complexity of the planar directed edge-disjoint paths problem
• Edge routing with ordered bundles
• Multiflow Feasibility: An Annotated Tableau
• BFS Solution for Disjoint Paths in P Systems
• An Excluded Minor Characterization of Seymour Graphs
• Tight bounds for linkages in planar graphs
• scientific article; zbMATH DE number 2086258 (Why is no real title available?)
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• scientific article; zbMATH DE number 4191702 (Why is no real title available?)
• An improved algorithm for the half-disjoint paths problem
• scientific article; zbMATH DE number 3876620 (Why is no real title available?)
• scientific article; zbMATH DE number 4202293 (Why is no real title available?)
• scientific article; zbMATH DE number 4204383 (Why is no real title available?)
• A linear time algorithm for finding three edge-disjoint paths in Eulerian networks
• Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
• Irrelevant vertices for the planar disjoint paths problem
• Towards single face shortest vertex-disjoint paths in undirected planar graphs
• The complexity of the edge disjoint multiple paths problem when constructed over uniformly directed mesh graphs
• Disjoint Paths—A Survey
• scientific article; zbMATH DE number 16298 (Why is no real title available?)
• scientific article; zbMATH DE number 47435 (Why is no real title available?)
• The disjoint paths problem in quadratic time
• Two Arc-Disjoint Paths in Eulerian Digraphs
• scientific article; zbMATH DE number 727422 (Why is no real title available?)
• A nearly linear time algorithm for the half integral parity disjoint paths packing problem
• Criticality for multicommodity flows
• On the tractability of some natural packing, covering and partitioning problems
• Orientations of graphs with prescribed weighted out-degrees
• scientific article; zbMATH DE number 1409242 (Why is no real title available?)
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
• Shortest k-disjoint paths via determinants
• scientific article; zbMATH DE number 7561410 (Why is no real title available?)
• The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
• The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
• Maximum Edge-Disjoint Paths Problem in Planar Graphs
• The widestk-set of disjoint paths problem
• The complexity of path coloring and call scheduling
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• 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
• Approximating maximum integral multiflows on bounded genus graphs
• Finding edge-disjoint paths in partial k-trees
• NP-completeness of the Eulerian walk problem for a multiple graph
• Temporal segmentation in multi agent path finding with applications to explainability
• The hardness of routing two pairs on one face
• An improved integrality gap for disjoint cycles in planar graphs
• Some polynomial subclasses of the Eulerian walk problem for a multiple graph
• Packing cycles in planar and bounded-genus graphs
• The complexity of decomposing a graph into a matching and a bounded linear forest
• Complexity framework for forbidden subgraphs. I: The framework
• Minimal multicut and maximal integer multiflow: a survey
• Multiflows in symmetric digraphs
• The indefinite period traveling salesman problem
• Approximating maximum integral multiflows on bounded genus graphs
• Packing paths in planar graphs
• Disjoint paths in sparse graphs

This page was built for publication: On the complexity of the disjoint paths problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2367446)