An improved algorithm for transitive closure on acyclic digraphs

DOI10.1016/0304-3975(88)90032-1zbMath0656.68047OpenAlexW2017139167MaRDI QIDQ1110330

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

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

Related Items (11)

Unnamed Item ⋮ \(q\)-distributions and Markov processes ⋮ The complexity of embedding orders into small products of chains ⋮ A Path Cover Technique for LCAs in Dags ⋮ An analytic approach to the asymptotic variance of trie statistics and related structures ⋮ Sharing the cost of maximum quality optimal spanning trees ⋮ On the calculation of transitive reduction-closure of orders ⋮ An Abstract Domain Extending Difference-Bound Matrices with Disequality Constraints ⋮ Generalized Polychotomic Encoding: A Very Short Bit-Vector Encoding of Tree Hierarchies ⋮ Acyclic Digraphs ⋮ Algorithms for transitive closure

Cites Work

• Approximate counting: a detailed analysis
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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