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

DOI10.1016/J.JCSS.2010.08.012zbMATH Open1233.68149OpenAlexW1997781700MaRDI QIDQ657914FDOQ657914

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

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

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)

Cites Work

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

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)