Boolean matrix multiplication and transitive closure
- 1 October 1971
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02724847,p. 129-131
- https://doi.org/10.1109/swat.1971.4
Abstract
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.Keywords
This publication has 3 references indexed in Scilit:
- A transitive closure algorithmBIT Numerical Mathematics, 1970
- Gaussian elimination is not optimalNumerische Mathematik, 1969
- A Theorem on Boolean MatricesJournal of the ACM, 1962