Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n 2 barrier

DOI10.1145/1059513.1059514zbMATH Open1316.68058DBLPjournals/jacm/DemetrescuI05OpenAlexW1969485351WikidataQ61609605 ScholiaQ61609605MaRDI QIDQ3546293FDOQ3546293

Authors: Camil Demetrescu, Giuseppe F. Italiano 

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

Recommendations

• A faster and simpler fully dynamic transitive closure
• scientific article; zbMATH DE number 2079364
• Mantaining dynamic matrices for fully dynamic transitive closure
• A fully dynamic algorithm for maintaining the transitive closure
• Improved Dynamic Reachability Algorithms for Directed Graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Cited In (8)

• Dynamic connectivity for axis-parallel rectangles
• Fast dynamic transitive closure with lookahead
• Speeding up dynamic transitive closure for bounded degree graphs
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
• Fully Dynamic Transitive Closure in plane dags with one source and one sink
• Mantaining dynamic matrices for fully dynamic transitive closure
• Tight bounds for the performance of Longest In System on DAGs

This page was built for publication: Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n ² barrier

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546293)