Hardness of Finding Two Edge-Disjoint Min-Min Paths in Digraphs

DOI10.1007/978-3-642-21204-8_32zbMath1329.68124OpenAlexW161149752MaRDI QIDQ3004683

Longkun Guo, Hong Shen

Publication date: 3 June 2011

Published in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-21204-8_32

zbMATH Keywords

NP-completenessinapproximabilitydisjoint pathplanar digraphMin-Min problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

On finding Min-Min disjoint paths

Cites Work

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

This page was built for publication: Hardness of Finding Two Edge-Disjoint Min-Min Paths in Digraphs