The input/output complexity of transitive closure

DOI10.1007/BF01530929zbMath0875.68239MaRDI QIDQ1360681

Mihalis Yannakakis, Jeffrey D. Ullman

Publication date: 26 October 1997

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

transitive closure

Mathematics Subject Classification ID

Logic programming (68N17)

Related Items (8)

Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep ⋮ External matrix multiplication and all-pairs shortest path ⋮ Blocking for external graph searching ⋮ Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep versus plane sweep ⋮ Turing machines with two-level memory: a deep look into the input/output complexity ⋮ Turing machines with two-level memory: new computational models for analyzing the input/output complexity ⋮ Solving path problems on the GPU ⋮ Computationally efficient sup-t transitive closure for sparse fuzzy binary relations

Uses Software

• Algorithm 447

Cites Work

• Matrix multiplication via arithmetic progressions
• A modification of Warshall's algorithm for the transitive closure of binary relations
• Dividing a Graph into Triconnected Components
• Organizing matrices and matrix operations for paged memory systems
• A Theorem on Boolean Matrices
• Unnamed Item
• Unnamed Item

This page was built for publication: The input/output complexity of transitive closure