On the complexity of the disjoint paths problem

DOI10.1007/BF01202792zbMATH Open0770.68072OpenAlexW2041884875MaRDI QIDQ2367446FDOQ2367446

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

Recommendations

• scientific article; zbMATH DE number 47435
• Publication:3211338
• 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

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) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cites Work

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

Cited In (73)

• Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
• Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs
• Tight integral duality gap in the Chinese postman problem
• Title not available (Why is that?)
• The disjoint shortest paths problem
• Disjoint paths in sparse graphs
• Finding edge-disjoint paths in networks: an ant colony optimization algorithm
• Solving the edge‐disjoint paths problem using a two‐stage method
• A polynomial-time algorithm for detecting the possibility of Braess paradox in directed graphs
• Minimal multicut and maximal integer multiflow: a survey
• The disjoint paths problem in quadratic time
• The complexity of path coloring and call scheduling
• The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
• Edge routing with ordered bundles
• Vertex disjoint paths on clique-width bounded graphs
• Multiflows in symmetric digraphs
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• BFS Solution for Disjoint Paths in P Systems
• Approximations for the disjoint paths problem in high-diameter planar networks
• On the complexity of the planar directed edge-disjoint paths problem
• A note on packing paths in planar graphs
• Disjoint paths in symmetric digraphs
• The indefinite period traveling salesman problem
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
• On the maximum degree of path-pairable planar graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Precoloring extension on unit interval graphs
• Disjoint Paths—A Survey
• On the complexity of vertex-disjoint length-restricted path problems
• On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary
• Criticality for multicommodity flows
• On the tractability of some natural packing, covering and partitioning problems
• A linear time algorithm for finding three edge-disjoint paths in Eulerian networks
• Finding edge-disjoint paths in partial k-trees
• Irrelevant vertices for the planar disjoint paths problem
• Parallel complexity of computing a maximal set of disjoint paths
• Orientations of graphs with prescribed weighted out-degrees
• Multiflow Feasibility: An Annotated Tableau
• Title not available (Why is that?)
• Max-multiflow/min-multicut for G+H series-parallel
• An Excluded Minor Characterization of Seymour Graphs
• Edge-disjoint paths in planar graphs
• Tight bounds for linkages in planar graphs
• The complexity of planar graph choosability
• On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms
• General vertex disjoint paths in series-parallel graphs
• Complexity of path discovery game problems
• The hardness of routing two pairs on one face
• Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
• The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
• An improved algorithm for the half-disjoint paths problem
• Eulerian disjoint paths problem in grid graphs is NP-complete
• Integer plane multiflow maximisation: one-quarter-approximation and gaps
• NP-completeness of some edge-disjoint paths problems
• Complexity of the path avoiding forbidden pairs problem revisited
• Maximum Edge-Disjoint Paths Problem in Planar Graphs
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• The widestk-set of disjoint paths problem
• Title not available (Why is that?)
• Temporal segmentation in multi agent path finding with applications to explainability
• Approximating maximum integral multiflows on bounded genus graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of the edge disjoint multiple paths problem when constructed over uniformly directed mesh graphs
• On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems
• Combing a Linkage in an Annulus
• Towards single face shortest vertex-disjoint paths in undirected planar graphs
• NP-completeness of the Eulerian walk problem for a multiple graph
• Title not available (Why is that?)
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• Title not available (Why is that?)

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)