A note on approximating the min-max vertex disjoint paths on directed acyclic graphs

DOI10.1016/J.JCSS.2010.08.012MaRDI QIDQ657914zbMATH OpenOpenAlexFDO

Authors Bang Ye Wu

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

zbMATH Keywords

directed acyclic graphapproximation algorithmFPTASroundingvertex disjoint path

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Paths and cycles (05C38)

Recommendations

• Efficient Algorithms for k-Disjoint Paths Problems on DAGs
• 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
• On the disjoint paths problem
• Graph-Theoretic Concepts in Computer Science
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems

Cites work

• A simple efficient approximation scheme for the restricted shortest path problem
• An improved FPTAS for Restricted Shortest Path.
• Approximation Schemes for the Restricted Shortest Path Problem
• Efficient Algorithms for k-Disjoint Paths Problems on DAGs
• 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
• Length-bounded disjoint paths in planar graphs
• The complexity of finding two disjoint paths with min-max objective function

Cited in

(4)

• Redundancy elimination in the estimation of multiple paths
• An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs
• On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks
• Efficient Algorithms for k-Disjoint Paths Problems on DAGs

This page was built for publication: A note on approximating the min-max vertex disjoint paths on directed acyclic graphs

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