Linear time algorithms for two disjoint paths problems on directed acyclic graphs
From MaRDI portal
Publication:1929240
DOI10.1016/j.tcs.2012.09.025zbMath1256.68133OpenAlexW2076850117MaRDI 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
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)
Related Items
Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths ⋮ Approximating the smallest 2-vertex connected spanning subgraph of a directed graph ⋮ Dynamic Dominators and Low-High Orders in DAGs
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
