A practical algorithm for Boolean matrix multiplication
From MaRDI portal
An algorithm is given for multiplying two \(n\times n\) Boolean matrices. It has time complexity \(O(n^ 3/(\log n)^{1.5})\) and requires n \(log_ 2 n\) bits of auxiliary storage.
Cites work
- A note on Boolean matrix multiplication
- An improved algorithm for Boolean matrix multiplication
- scientific article; zbMATH DE number 3800924 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- scientific article; zbMATH DE number 3340123 (Why is no real title available?)
- Improved time and space bounds for Boolean matrix multiplication
Cited in
(9)- An efficient algorithm for calculating Boolean difference
- Design of cellular manufacturing systems based on asymptotic forms of a Boolean matrix
- On the use of the asymptotic forms of the Boolean matrix for designing cellular manufacturing systems. -- An improved approach
- An efficiently solvable graph partition problem to which many problems are reducible
- scientific article; zbMATH DE number 1223727 (Why is no real title available?)
- scientific article; zbMATH DE number 1979525 (Why is no real title available?)
- N latency 2N I/O‐bandwidth 2D‐array matrix multiplication algorithm
- The Closest Pair Problem under the Hamming Metric
- Fast multiplication of matrices over a finitely generated semiring
This page was built for publication: A practical algorithm for Boolean matrix multiplication
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111377)
