Hardness of finding two edge-disjoint Min-Min paths in digraphs

DOI10.1007/978-3-642-21204-8_32MaRDI QIDQ3004683zbMATH OpenOpenAlexFDO

Authors 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-completenessdisjoint pathinapproximabilityplanar digraphMin-Min problem

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of the edge-disjoint min-min problem in planar digraphs
• On finding Min-Min disjoint paths
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
• Complexity and approximation results for the min-sum and min-max disjoint paths problems
• The complexity of finding two disjoint paths with min-max objective function

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 Planar Graph—A General Theorem
• Disjoint paths in a network
• Disjoint paths in graphs. (Reprint)
• 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

(5)

• The complexity of finding two disjoint paths with min-max objective function
• Hardness of minimum barrier shrinkage and minimum installation path
• On the complexity of the edge-disjoint min-min problem in planar digraphs
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
• On finding Min-Min disjoint paths

This page was built for publication: Hardness of finding two edge-disjoint Min-Min paths in digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3004683)