Complexity and approximation results for the min-sum and min-max disjoint paths problems
From MaRDI portal
Publication:4610074
zbMATH Open1413.68062MaRDI QIDQ4610074FDOQ4610074
Authors: Peng Zhang, Wen-Bo Zhao, Daming Zhu 
Publication date: 5 April 2018
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Paths and cycles (05C38)
Cited In (15)
- On shortest disjoint paths in planar graphs
- Efficient algorithms for minimal disjoint path problems on chordal graphs
- On the bit complexity of minimum link paths: Superquadratic algorithms for problem solvable in linear time
- Hardness of finding two edge-disjoint Min-Min paths in digraphs
- Approximability of 3- and 4-Hop Bounded Disjoint Paths Problems
- Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience
- On the complexity of vertex-disjoint length-restricted path problems
- The checkpoint problem
- Min-sum 2-paths problems
- Parallel complexity of computing a maximal set of disjoint paths
- Finding disjoint paths with different path-costs: Complexity and algorithms
- On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
- The checkpoint problem
- Approximating disjoint-path problems using packing integer programs
- Title not available (Why is that?)
This page was built for publication: Complexity and approximation results for the min-sum and min-max disjoint paths problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4610074)
