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

transitive closuretime and space complexityrandom acyclic digraphs

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)

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

• 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?)
• Approximate counting: a detailed analysis

Cited in

(21)

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

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)