The input/output complexity of transitive closure

DOI10.1007/BF01530929MaRDI QIDQ1360681zbMATH OpenFDO

Authors Jeffrey D. Ullman, Mihalis Yannakakis

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)

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3225079 (Why is no real title available?)
• A Theorem on Boolean Matrices
• A modification of Warshall's algorithm for the transitive closure of binary relations
• Dividing a Graph into Triconnected Components
• Matrix multiplication via arithmetic progressions
• Organizing matrices and matrix operations for paged memory systems

Cited in

(8)

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

Describes a project that uses

Uses Software

• Algorithm 447

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

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