Improved Dynamic Reachability Algorithms for Directed Graphs
From MaRDI portal
Recommendations
- A faster and simpler fully dynamic transitive closure
- scientific article; zbMATH DE number 2079364
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- A fully dynamic algorithm for maintaining the transitive closure
Cited in
(40)- Reachability preserving compression for dynamic graph
- Reachability Problems on Directed Graphs
- Average case analysis of fully dynamic connectivity for directed graphs
- Finding paths and deleting edges in directed acyclic graphs
- O’Reach: Even Faster Reachability in Large Graphs
- scientific article; zbMATH DE number 7561709 (Why is no real title available?)
- Faster fully dynamic transitive closure in practice
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Fast dynamic transitive closure with lookahead
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- Fully dynamic maximal matching in O( n) update time (corrected version)
- A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph
- An improved algorithm for incremental DFS tree in undirected graphs
- Decremental SPQR-trees for Planar Graphs
- Reachability in graph timelines
- Average case analysis of fully dynamic reachability for directed graphs
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
- Incremental algorithm for maintaining a DFS tree for undirected graphs
- Dynamic graph coloring
- Spanners and Reachability Oracles for Directed Transmission Graphs
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- Fault tolerant reachability for directed graphs
- Randomization for efficient dynamic graph algorithms (invited talk)
- On Dynamic DFS Tree in Directed Graphs
- Space-efficient algorithms for reachability in directed geometric graphs
- On dynamic shortest paths problems
- Fully dynamic strongly connected components in planar digraphs
- Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
- Fully dynamic maximal matching in O( n) update time
- Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n 2 barrier
- Decremental strongly connected components and single-source reachability in near-linear time
- O'Reach: Even Faster Reachability in Large Graphs
- Maintaining shortest paths under deletions in weighted directed graphs
- A fully dynamic algorithm for maintaining the transitive closure
- A fully dynamic algorithm for maintaining the transitive closure
- An efficient strongly connected components algorithm in the fault tolerant model
- Incremental dead state detection in logarithmic time
This page was built for publication: Improved Dynamic Reachability Algorithms for Directed Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3532572)
