An improved algorithm for Boolean matrix multiplication |
| |
| Authors: | Dr N Santoro Dr J Urrutia |
| |
| Affiliation: | 1. School of Computer Science, Carleton University, K1S 5B6, Ottawa, Canada
2. Computer Science Department, University of Ottawa, K1N 5B4, Ottawa, Canada
|
| |
| Abstract: | A new algorithm for computing the product of two arbitraryN×N Boolean matrices is presented. The algorithm requiresO (N 3/logN) bit operations and onlyO(N logN) bits of additional storage. This represents an improvement on the Four Russians' method which requires the same number of operations but usesO(N 3/logN) bits of additional storage. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
