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

DOI10.1145/1059513.1059514MaRDI QIDQ3546293zbMATH OpenOpenAlexDBLPWikidataFDO

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

Mathematics Subject Classification ID

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

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

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
• Mantaining dynamic matrices for fully dynamic transitive closure
• Fully Dynamic Transitive Closure in plane dags with one source and one sink
• 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)