A fully dynamic reachability algorithm for directed graphs with an almost linear update time
From MaRDI portal
Publication:3580968
DOI10.1145/1007352.1007387zbMath1192.90238OpenAlexW2139666321MaRDI QIDQ3580968
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
Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (12)
Fast dynamic transitive closure with lookahead ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ A Dynamic Algorithm for Reachability Games Played on Trees ⋮ Connectivity games over dynamic networks ⋮ Linear time analysis of properties of conflict-free and general Petri nets ⋮ On dynamic shortest paths problems ⋮ Average update times for fully-dynamic all-pairs shortest paths ⋮ Average-Case Analysis of Online Topological Ordering ⋮ \(f\)-sensitivity distance oracles and routing schemes ⋮ Average-case analysis of incremental topological ordering ⋮ A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time ⋮ Dynamic connectivity for axis-parallel rectangles
This page was built for publication: A fully dynamic reachability algorithm for directed graphs with an almost linear update time
