Finding paths and deleting edges in directed acyclic graphs
From MaRDI portal
Publication:1115184
DOI10.1016/0020-0190(88)90136-6zbMath0663.68052OpenAlexW2037034819WikidataQ61609677 ScholiaQ61609677MaRDI QIDQ1115184
Publication date: 1988
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(88)90136-6
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs ⋮ NC algorithms for dynamically solving the all pairs shortest paths problem and related problems ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ A data structure for arc insertion and regular path finding ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ On-line graph algorithms for incremental compilation ⋮ Average case analysis of fully dynamic connectivity for directed graphs ⋮ Dynamic maintenance of planar digraphs, with applications ⋮ Complexity of the path avoiding forbidden pairs problem revisited ⋮ Mantaining dynamic matrices for fully dynamic transitive closure ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ Maintenance of 2- and 3-edge-connected components of graphs. I ⋮ Dynamic reachability in planar digraphs with one source and one sink ⋮ On the complexity of paths avoiding forbidden pairs ⋮ A fully dynamic algorithm for maintaining the transitive closure ⋮ Maintenance of triconnected components of graphs ⋮ A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time ⋮ A uniform approach to semi-dynamic problems on digraphs ⋮ Average case analysis of fully dynamic reachability for directed graphs ⋮ Maintaining a topological order under edge insertions ⋮ Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time ⋮ Lifelong planning \(\text{A}^*\) ⋮ Speeding up dynamic transitive closure for bounded degree graphs
Cites Work
- On-line computation of transitive closures of graphs
- Amortized efficiency of a path retrieval data structure
- Parallel concepts in graph theory
- A data structure for dynamic trees
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Amortized Computational Complexity
- Worst-case Analysis of Set Union Algorithms
- An On-Line Edge-Deletion Problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
