A practical algorithm for Boolean matrix multiplication (Q1111377)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A practical algorithm for Boolean matrix multiplication |
scientific article |
Statements
A practical algorithm for Boolean matrix multiplication (English)
0 references
1988
0 references
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.
0 references
Boolean matrix multiplication
0 references
time versus storage tradeoffs
0 references
