On the complexity of the edge-disjoint min-min problem in planar digraphs

DOI10.1016/J.TCS.2011.12.009MaRDI QIDQ428855zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

disjoint pathinapproximabilityNP-completemin-min problemplanar digraph

Mathematics Subject Classification ID

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)

Recommendations

• Hardness of finding two edge-disjoint Min-Min paths in digraphs
• On finding Min-Min disjoint paths
• On the complexity of the planar directed edge-disjoint paths problem
• NP-completeness of some edge-disjoint paths problems
• The disjoint shortest paths problem

Cites work

• A Polynomial Solution to the Undirected Two Paths Problem
• A quick method for finding shortest pairs of disjoint paths
• Disjoint paths in a network
• Disjoint paths in graphs. (Reprint)
• Efficient Planarity Testing
• Finding k Disjoint Paths in a Directed Planar Graph
• Finding disjoint paths with different path-costs: Complexity and algorithms
• Finding disjoint paths with related path costs
• Length-bounded disjoint paths in planar graphs
• On finding Min-Min disjoint paths
• The complexity of finding two disjoint paths with min-max objective function
• The directed subgraph homeomorphism problem

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)