A fully dynamic reachability algorithm for directed graphs with an almost linear update time
DOI10.1145/1007352.1007387zbMATH Open1192.90238OpenAlexW2139666321MaRDI QIDQ3580968FDOQ3580968
Publication date: 15 August 2010
Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1007352.1007387
Recommendations
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- Improved Dynamic Reachability Algorithms for Directed Graphs
- Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
- A faster and simpler fully dynamic transitive closure
- scientific article; zbMATH DE number 2079364
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)
Cited In (17)
- Connectivity games over dynamic networks
- Dynamic connectivity for axis-parallel rectangles
- \(f\)-sensitivity distance oracles and routing schemes
- Fast dynamic transitive closure with lookahead
- Improved Dynamic Reachability Algorithms for Directed Graphs
- Average case analysis of fully dynamic reachability for directed graphs
- An $$O(n^{\epsilon })$$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
- Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- On dynamic shortest paths problems
- Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
- Average-case analysis of incremental topological ordering
- An O ( n ϵ ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
- Average update times for fully-dynamic all-pairs shortest paths
- A Dynamic Algorithm for Reachability Games Played on Trees
- Linear time analysis of properties of conflict-free and general Petri nets
- Average-Case Analysis of Online Topological Ordering
This page was built for publication: A fully dynamic reachability algorithm for directed graphs with an almost linear update time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580968)
