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 等数据库收录! |
|