1971/10/01 by Michael J. Fischer, Albert R. Meyer · 3 citations
Computer Science · Mathematics · #Coding theory and cryptography #Commutative Algebra and Its Applications #Polynomial and algebraic computation #Transitive closure #Strassen algorithm #Bitwise operation #Mathematics #Closure (psychology) #Matrix multiplication #Transitive relation #Logical matrix #Matrix (chemical analysis) #Discrete mathematics #Multiplication (music) #Combinatorics #Modulo #Computer science #Group (periodic table)
paper · doi:10.1109/swat.1971.4
openalex publication_date 1971/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.