An improved algorithm for transitive closure on acyclic digraphs

DOI10.1016/0304-3975(88)90032-1MaRDI QIDQ1110330zbMATH OpenOpenAlexFDO

Authors Klaus Simon

Publication date 1988

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(88)90032-1

zbMATH Keywords

random acyclic digraphstime and space complexitytransitive closure

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

The author improves the time and space complexity worst-case bounds of \textit{A. Goralčíková} and \textit{V. Koubek}'s algorithm for transitive closure of acyclic digraphs [Lect. Notes Comput. Sci. 74, 301- 307 (1979; Zbl 0408.68038)]. Further, some expected complexity bounds are derived in a model of random acyclic digraphs.

Recommendations

• scientific article; zbMATH DE number 3958732
• scientific article; zbMATH DE number 6783482
• Algorithms for transitive closure
• scientific article; zbMATH DE number 813252
• An algorithm for transitive reduction of an acyclic graph
• An experimental study of dynamic algorithms for transitive closure
• A fully dynamic algorithm for maintaining the transitive closure
• A fully dynamic algorithm for maintaining the transitive closure
• An experimental study of algorithms for fully dynamic transitive closure

Cites work

• Approximate counting: a detailed analysis
• scientific article; zbMATH DE number 3887060 (Why is no real title available?)
• scientific article; zbMATH DE number 3871260 (Why is no real title available?)
• scientific article; zbMATH DE number 3747020 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 3635493 (Why is no real title available?)

Cited in

(22)

• An algorithm for transitive reduction of an acyclic graph
• Speeding up dynamic transitive closure for bounded degree graphs
• A new variant of the \(A^*\)-algorithm which closes a node at most once.
• \(q\)-distributions and Markov processes
• Algorithms for transitive closure
• Sharing the cost of maximum quality optimal spanning trees
• An analytic approach to the asymptotic variance of trie statistics and related structures
• A phase transition phenomenon in a random directed acyclic graph
• Acyclic digraphs
• scientific article; zbMATH DE number 3866595 (Why is no real title available?)
• A Path Cover Technique for LCAs in Dags
• Generalized Polychotomic Encoding: A Very Short Bit-Vector Encoding of Tree Hierarchies
• scientific article; zbMATH DE number 3958732 (Why is no real title available?)
• Complexité de problèmes liés aux graphes sans circuit
• scientific article; zbMATH DE number 1208713 (Why is no real title available?)
• Transitive closure and transitive reduction in bidirected graphs
• scientific article; zbMATH DE number 6783482 (Why is no real title available?)
• An Abstract Domain Extending Difference-Bound Matrices with Disequality Constraints
• The complexity of embedding orders into small products of chains
• On the calculation of transitive reduction-closure of orders
• Acyclic networks maximizing the printing complexity
• Parameterized linear time transitive closure

This page was built for publication: An improved algorithm for transitive closure on acyclic digraphs

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