Boolean matrix multiplication and transitive closure
Michael J. Fischer, Albert R. Meyer · 1971
Arithmetic operations on matrices are applied to the problem of finding the transitive closure of a Boolean matrix. The best transitive closure algorithm known, due to Munro, is based on the matrix multiplication method of Strassen. We show that his method requires at most O(nα· P(n)) bitwise operations, where α = log27 and P(n) bounds the number of bitwise operations needed for arithmetic modulo n+1. The problems of computing the transitive closure and of computing the "and-or" product of Boolean matrices are shown to be of the same order of difficulty. A transitive closure method based on matrix inverse is presented which can be used to derive Munro's method.