On the complexity of the edge-disjoint min-min problem in planar digraphs
DOI10.1016/J.TCS.2011.12.009zbMATH Open1242.68114OpenAlexW2049003114MaRDI QIDQ428855FDOQ428855
Authors: Longkun Guo, Hong Shen 
Publication date: 25 June 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.009
Recommendations
Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cites Work
- The directed subgraph homeomorphism problem
- A Polynomial Solution to the Undirected Two Paths Problem
- Efficient Planarity Testing
- The complexity of finding two disjoint paths with min-max objective function
- Disjoint paths in a network
- A quick method for finding shortest pairs of disjoint paths
- On finding Min-Min disjoint paths
- Finding disjoint paths with related path costs
- Finding k Disjoint Paths in a Directed Planar Graph
- Finding disjoint paths with different path-costs: Complexity and algorithms
- Length-bounded disjoint paths in planar graphs
- Disjoint paths in graphs. (Reprint)
Cited In (8)
- The complexity of finding two disjoint paths with min-max objective function
- Hardness of finding two edge-disjoint Min-Min paths in digraphs
- The Vertex-Disjoint Menger Problem in Planar Graphs
- Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths
- On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary
- Improved approximation algorithms for computing \(k\) disjoint paths subject to two constraints
- On finding Min-Min disjoint paths
- NP-completeness of some edge-disjoint paths problems
This page was built for publication: On the complexity of the edge-disjoint min-min problem in planar digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428855)
