A discussion of explicit methods for transitive closure computation based on matrix multiplication

Arithmetic operations on matrices are applied to the problem of finding the transitive closure of a Boolean matrix. The best transitive closure algorithm known is based on the matrix multiplication method of Strassen (1959). It has been shown that this method requires, at most, O(n/sup /spl alpha///spl middot/P(n)) bit-wise operations, where /spl alpha/=log/sub 2/ 7, and P(n) bounds the number of bitwise operations needed for arithmetic module n+1. The problems of computing the transitive closure and computing the and-or product of Boolean matrices can then be considered of the same order of difficulty.