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, Chih-Chiang Yu, Chien-Hsin Lin
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
algorithms; dynamic programming; planar graphs; directed acyclic graphs; vertex-disjoint paths; pseudo-polynomial time; fully polynomial-time approximation schemes
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
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
