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.05059OpenAlexW2093083747MaRDI 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

algorithmsdynamic programmingplanar graphsdirected acyclic graphsvertex-disjoint pathspseudo-polynomial timefully polynomial-time approximation schemes

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

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

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

This page was built for publication: 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