Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n 2 barrier
From MaRDI portal
Publication:3546293
DOI10.1145/1059513.1059514zbMath1316.68058OpenAlexW1969485351WikidataQ61609605 ScholiaQ61609605MaRDI QIDQ3546293
Giuseppe F. Italiano, Camil Demetrescu
Publication date: 21 December 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1059513.1059514
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items
Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ Mantaining dynamic matrices for fully dynamic transitive closure ⋮ A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time ⋮ Dynamic connectivity for axis-parallel rectangles
