A fully dynamic algorithm for maintaining the transitive closure

DOI10.1145/301250.301380MaRDI QIDQ5890868zbMATH OpenOpenAlexFDO

Authors Valerie King, Garry Sagert

Publication date 29 September 2016

Published in Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/301250.301380

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

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

Cited in

(13)

• An improved algorithm for transitive closure on acyclic digraphs
• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• Associative version of Italiano's incremental algorithm for dynamic updating the transitive closure
• A dynamic topological sort algorithm for directed acyclic graphs
• Improved Dynamic Reachability Algorithms for Directed Graphs
• The research of dynamic transitive closure algorithm for complex networks
• scientific article; zbMATH DE number 4083002 (Why is no real title available?)
• scientific article; zbMATH DE number 2079364 (Why is no real title available?)
• scientific article; zbMATH DE number 2080476 (Why is no real title available?)
• A faster and simpler fully dynamic transitive closure
• A fully dynamic algorithm for maintaining the transitive closure
• Computing transitive closure on systolic arrays of fixed size
• Mantaining dynamic matrices for fully dynamic transitive closure

This page was built for publication: A fully dynamic algorithm for maintaining the transitive closure

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