A note on approximating the min-max vertex disjoint paths on directed acyclic graphs
From MaRDI portal
Publication:657914
DOI10.1016/j.jcss.2010.08.012zbMath1233.68149MaRDI QIDQ657914
Publication date: 11 January 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2010.08.012
68Q25: Analysis of algorithms and problem complexity
05C38: Paths and cycles
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Cites Work
- The complexity of finding two disjoint paths with min-max objective function
- Length-bounded disjoint paths in planar graphs
- An improved FPTAS for Restricted Shortest Path.
- Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph
- Approximation Schemes for the Restricted Shortest Path Problem
- Efficient Algorithms for k-Disjoint Paths Problems on DAGs
- A simple efficient approximation scheme for the restricted shortest path problem