# Lund University Publications

## LUND UNIVERSITY LIBRARIES

### Fast Boolean matrix multiplication for highly clustered data

and Lingas, Andrzej LU (2001) In Algorithms and data structures : 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001 : proceedings LNCS 2125. p.258-263
Abstract
We consider the problem of computing the product of two

n×n Boolean matrices A and B. For an n×n Boolean matrix C, let GC

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 ﬁrst row having values diﬀerent from the corresponding

entries in the second one. Next, letMWT(C) be the weight of a minimum

weight spanning tree of GC. We show that the product of A with B as

well as the so called witnesses of the product can be computed in time

(n(n + min{MWT(A),MWT(Bt)}))

˜O
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Algorithms and data structures : 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001 : proceedings
volume
LNCS 2125
pages
258 - 263
publisher
Springer
external identifiers
• Scopus:84958053511
ISBN
3540424237
DOI
10.1007/3-540-44634-6_24
language
English
LU publication?
yes
id
62718902-8a17-4700-887a-3cf62f717944 (old id 526578)
2007-09-13 12:26:54
date last changed
2016-10-13 04:43:42
```@misc{62718902-8a17-4700-887a-3cf62f717944,
abstract     = {We consider the problem of computing the product of two<br/><br>
n×n Boolean matrices A and B. For an n×n Boolean matrix C, let GC<br/><br>
be the complete weighted graph on the rows of C where the weight of an<br/><br>
edge between two rows is equal to its Hamming distance, i.e., the number<br/><br>
of entries in the ﬁrst row having values diﬀerent from the corresponding<br/><br>
entries in the second one. Next, letMWT(C) be the weight of a minimum<br/><br>
weight spanning tree of GC. We show that the product of A with B as<br/><br>
well as the so called witnesses of the product can be computed in time<br/><br>
(n(n + min{MWT(A),MWT(Bt)}))<br/><br>
˜O},
author       = {Björklund, Andreas and Lingas, Andrzej},
isbn         = {3540424237},
language     = {eng},
pages        = {258--263},
publisher    = {ARRAY(0x7ff5010)},
series       = {Algorithms and data structures : 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001 : proceedings},
title        = {Fast Boolean matrix multiplication for highly clustered data},
url          = {http://dx.doi.org/10.1007/3-540-44634-6_24},
volume       = {LNCS 2125},
year         = {2001},
}

```