Linear time algorithms for two disjoint paths problems on directed acyclic graphs
From MaRDI portal
Publication:1929240
DOI10.1016/j.tcs.2012.09.025zbMath1256.68133MaRDI QIDQ1929240
Publication date: 7 January 2013
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.09.025
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
68P05: Data structures
Related Items
Dynamic Dominators and Low-High Orders in DAGs, Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths, Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The disjoint paths problem in quadratic time
- The 2-linkage problem for acyclic digraphs
- The directed subgraph homeomorphism problem
- Disjoint paths in graphs
- 2-linked graphs
- Output-sensitive reporting of disjoint paths
- Rooted routing in the plane
- Maintaining the classes of 4-edge-connectivity in a graph on-line
- Graph minors. XIII: The disjoint paths problem
- Solving the 2-disjoint paths problem in nearly linear time
- Optimization of LR(k) parsers
- Dominators, Directed Bipolar Orders, and Independent Spanning Trees
- Fast Algorithms for Finding Nearest Common Ancestors
- A quick method for finding shortest pairs of disjoint paths
- Improved Algorithms for the 2-Vertex Disjoint Paths Problem
- Worst-case Analysis of Set Union Algorithms
- A Polynomial Solution to the Undirected Two Paths Problem
- Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
- Dominators in Linear Time
- Sparsification—a technique for speeding up dynamic graph algorithms
- Fibonacci heaps and their uses in improved network optimization algorithms
- AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
- Graph-Theoretic Concepts in Computer Science
