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

DOI10.1016/j.jcss.2010.01.013zbMath1213.05059MaRDI QIDQ1959418

Biing-Feng Wang, Chien-Hsin Lin, Chih-Chiang Yu

Publication date: 7 October 2010

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.01.013

zbMATH Keywords

algorithms; dynamic programming; planar graphs; directed acyclic graphs; vertex-disjoint paths; pseudo-polynomial time; fully polynomial-time approximation schemes

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

90C39: Dynamic programming

05C10: Planar graphs; geometric and topological aspects of graph theory

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

Related Items

A note on approximating the min-max vertex disjoint paths on directed acyclic graphs, On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks

Cites Work

• Unnamed Item
• An efficient algorithm for \(k\)-pairwise disjoint paths in star graphs
• The complexity of finding two disjoint paths with min-max objective function
• The maximum edge-disjoint paths problem in complete graphs
• The directed subgraph homeomorphism problem
• General vertex disjoint paths in series-parallel graphs
• An efficient algorithm for the \(k\)-pairwise disjoint paths problem in hypercubes
• Length-bounded disjoint paths in planar graphs
• A linear-time algorithm for edge-disjoint paths in planar graphs
• Graph minors. XIII: The disjoint paths problem
• Solving the 2-disjoint paths problem in nearly linear time
• Approximation Schemes for the Restricted Shortest Path Problem
• On the Computational Complexity of Combinatorial Problems
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• The complexity of finding maximum disjoint paths with length constraints
• Efficient Algorithms for k-Disjoint Paths Problems on DAGs