01830739

a

01830739 Bj\"orklund, Andreas Lingas, Andrzej Fast Boolean matrix multiplication for highly clustered data. Dehne, Frank (ed.) et al., Algorithms and data structures. 7th international workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2125, 258-263 (2001). 2001 Berlin: Springer EN

http://link.springer.de/link/service/series/0558/bibs/2125/21250258

Summary: We consider the problem of computing the product of two $n\times n$ Boolean matrices $A$ and $B$. For an $n\times n$ Boolean matrix $C$, let $G_C$ be the complete weighted graph on the rows of $C$ where the weight of an edge between two rows is equal to its Hamming distance, i.e., the number of entries in the first row having values different from the corresponding entries in the second one. Next, let $MWT(C)$ be the weight of a minimum weight spanning tree of $G_{C}$. We show that the product of $A$ with $B$ as well as the so-called witnesses of the product can be computed in time $\widetilde{O}(n(n + \min\{MWT(A), MWT(B^t)\}))$.