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