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.68149OpenAlexW1997781700MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
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
This page was built for publication: A note on approximating the min-max vertex disjoint paths on directed acyclic graphs