Efficient Algorithms for k-Disjoint Paths Problems on DAGs

DOI10.1007/978-3-540-72870-2_13MaRDI QIDQ5434432zbMATH OpenOpenAlexFDO

Authors Rudolf Fleischer, Q. Ge, Jian Li, Hong Zhu

Publication date 4 January 2008

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-72870-2_13

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Graph-Theoretic Concepts in Computer Science
• On the disjoint paths problem
• Finding disjoint paths with different path-costs: Complexity and algorithms
• A note on approximating the min-max vertex disjoint paths on directed acyclic graphs
• The Directed Disjoint Shortest Paths Problem

Cited in

(10)

• 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 listing \(k\) disjoint \(st\)-paths in graphs
• On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks
• Tight bounds for the performance of Longest In System on DAGs
• scientific article; zbMATH DE number 4205963 (Why is no real title available?)
• Curvature in image and shape processing
• Efficient algorithms for minimal disjoint path problems on chordal graphs
• Graph-Theoretic Concepts in Computer Science
• A note on approximating the min-max vertex disjoint paths on directed acyclic graphs
• On the approximability of train routing and the min-max disjoint paths problem

This page was built for publication: Efficient Algorithms for k-Disjoint Paths Problems on DAGs

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