On finding Min-Min disjoint paths

DOI10.1007/S00453-012-9656-0MaRDI QIDQ2375950zbMATH OpenOpenAlexFDO

Authors Longkun Guo, Hong Shen

Publication date 25 June 2013

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-012-9656-0

zbMATH Keywords

shortest pathNP-hardnessplanar graphpolynomial-time algorithmdisjoint pathsMin-Min problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

Recommendations

• Hardness of finding two edge-disjoint Min-Min paths in digraphs
• On the complexity of the edge-disjoint min-min problem in planar digraphs
• On shortest disjoint paths in planar graphs
• On shortest disjoint paths in planar graphs
• The disjoint shortest paths problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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)
• Edge-disjoint paths in planar graphs
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Finding disjoint paths with different path-costs: Complexity and algorithms
• Finding disjoint paths with related path costs
• Hardness of finding two edge-disjoint Min-Min paths in digraphs
• Length-bounded disjoint paths in planar graphs
• Some simplified NP-complete graph problems
• The complexity of finding two disjoint paths with min-max objective function

Cited in

(19)

• On the complexity of algorithms for detecting \(k\)-length negative cost cycles
• On shortest disjoint paths in planar graphs
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
• The complexity of finding two disjoint paths with min-max objective function
• Hardness of finding two edge-disjoint Min-Min paths in digraphs
• The minimum reload \(s-t\) path, trail and walk problems
• Hardness of minimum barrier shrinkage and minimum installation path
• Efficient algorithms for minimal disjoint path problems on chordal graphs
• On the complexity of the edge-disjoint min-min problem in planar digraphs
• Finding disjoint paths with related path costs
• Algorithms and Computation
• Finding paths with minimum shared edges
• On shortest disjoint paths in planar graphs
• Finding the Minimum-Weight k-Path
• Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths
• Minimum-link paths revisited
• Complexity and approximation results for the min-sum and min-max disjoint paths problems
• Finding Minors in Graphs with a Given Path Structure
• Improved approximation algorithms for computing \(k\) disjoint paths subject to two constraints

This page was built for publication: On finding Min-Min disjoint paths

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