On finding Min-Min disjoint paths
DOI10.1007/S00453-012-9656-0zbMATH Open1281.68125OpenAlexW2066450989MaRDI QIDQ2375950FDOQ2375950
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
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- A Polynomial Solution to the Undirected Two Paths Problem
- The complexity of finding two disjoint paths with min-max objective function
- Some simplified NP-complete graph problems
- Disjoint paths in a network
- Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
- A quick method for finding shortest pairs of disjoint paths
- Finding disjoint paths with related path costs
- Edge-disjoint paths in planar graphs
- Finding disjoint paths with different path-costs: Complexity and algorithms
- Length-bounded disjoint paths in planar graphs
- Disjoint paths in graphs. (Reprint)
- Hardness of finding two edge-disjoint Min-Min paths in digraphs
Cited In (19)
- On shortest disjoint paths in planar graphs
- Minimum-link paths revisited
- The complexity of finding two disjoint paths with min-max objective function
- Efficient algorithms for minimal disjoint path problems on chordal graphs
- Hardness of finding two edge-disjoint Min-Min paths in digraphs
- Hardness of minimum barrier shrinkage and minimum installation path
- On the complexity of algorithms for detecting \(k\)-length negative cost cycles
- Finding the Minimum-Weight k-Path
- Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths
- On the complexity of the edge-disjoint min-min problem in planar digraphs
- Finding disjoint paths with related path costs
- On shortest disjoint paths in planar graphs
- Finding paths with minimum shared edges
- Improved approximation algorithms for computing \(k\) disjoint paths subject to two constraints
- Complexity and approximation results for the min-sum and min-max disjoint paths problems
- Algorithms and Computation
- On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
- The minimum reload \(s-t\) path, trail and walk problems
- Finding Minors in Graphs with a Given Path Structure
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)
