Article

Boolean matrix multiplication and transitive closure

Authors:

M. J. Fischer,

A. R. MeyerAuthors Info & Claims

SWAT '71: Proceedings of the 12th Annual Symposium on Switching and Automata Theory (swat 1971)

Pages 129 - 131

https://doi.org/10.1109/SWAT.1971.4

Published: 13 October 1971 Publication History

Publisher Site

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.

Cited By

View all

Abboud AFischer NKelley ZLovett SMeka RMohar BShinkar IO'Donnell R(2024)New Graph Decompositions and Combinatorial Boolean Matrix Multiplication AlgorithmsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649696(935-943)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649696
Koutris PDeep S(2023)The Fine-Grained Complexity of CFL ReachabilityProceedings of the ACM on Programming Languages10.1145/35712527:POPL(1713-1739)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571252
Chan TVassilevska Williams VXu YSaha BServedio R(2023)Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and MoreProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585237(419-432)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585237
Show More Cited By

Index Terms

Boolean matrix multiplication and transitive closure
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Index terms have been assigned to the content through auto-classification.

Recommendations

Some New Designs of 2-D Array for Matrix Multiplication and Transitive Closure

In this paper, we present some new regular iterative algorithms for matrix multiplication and transitive closure. With these algorithms, by spacetime mapping the 2-D arrays with $2N - 1$ and $\lceil (3N - 1)/2\rceil$ execution times for matrix ...
Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract)
FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science

We consider dynamic evaluation of algebraic functions such as computing determinant, matrix adjoint, matrix inverse and solving linear system of equations. We show that in the dynamic setup the above problems can be solved faster than evaluating ...
A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication

We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast output-sensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SWAT '71: Proceedings of the 12th Annual Symposium on Switching and Automata Theory (swat 1971)

October 1971

218 pages

Publisher

IEEE Computer Society

United States

Publication History

Published: 13 October 1971

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Abboud AFischer NKelley ZLovett SMeka RMohar BShinkar IO'Donnell R(2024)New Graph Decompositions and Combinatorial Boolean Matrix Multiplication AlgorithmsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649696(935-943)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649696
Koutris PDeep S(2023)The Fine-Grained Complexity of CFL ReachabilityProceedings of the ACM on Programming Languages10.1145/35712527:POPL(1713-1739)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571252
Chan TVassilevska Williams VXu YSaha BServedio R(2023)Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and MoreProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585237(419-432)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585237
Chan TWilliams VXu YLeonardi SGupta A(2022)Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OVProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520032(1501-1514)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520032
Atre M(2022)The Case of SPARQL UNION, FILTER and DISTINCTProceedings of the ACM Web Conference 202210.1145/3485447.3511992(1882-1892)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3485447.3511992
Karppa MKaski PChan T(2019)Probabilistic tensors and opportunistic boolean matrix multiplicationProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310466(496-515)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310466
Williams VWilliams R(2018)Subcubic Equivalences Between Path, Matrix, and Triangle ProblemsJournal of the ACM10.1145/318689365:5(1-38)Online publication date: 29-Aug-2018
https://dl.acm.org/doi/10.1145/3186893
Chan TWilliams R(2016)Deterministic APSP, orthogonal vectors, and moreProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884522(1246-1255)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884522
Cheng CMcDermid ESuzuki I(2016)Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchingsDiscrete Applied Mathematics10.1016/j.dam.2015.11.016205:C(27-34)Online publication date: 31-May-2016
https://dl.acm.org/doi/10.1016/j.dam.2015.11.016
Jeffery SKothari RLe Gall FMagniez F(2016)Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph CollisionAlgorithmica10.1007/s00453-015-9985-x76:1(1-16)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s00453-015-9985-x
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

Some New Designs of 2-D Array for Matrix Multiplication and Transitive Closure

Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract)

A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations