Fast Boolean matrix multiplication for highly clustered data
(2001) In Algorithms and data structures : 7th International Workshop, WADS 2001, Providence, RI, USA, August 810, 2001 : proceedings LNCS 2125. p.258263 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
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/526578
 author
 Björklund, Andreas ^{LU} and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2001
 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 810, 2001 : proceedings
 volume
 LNCS 2125
 pages
 258  263
 publisher
 Springer
 external identifiers

 scopus:84958053511
 ISBN
 3540424237
 DOI
 10.1007/3540446346_24
 language
 English
 LU publication?
 yes
 id
 627189028a174700887a3cf62f717944 (old id 526578)
 date added to LUP
 20070913 12:26:54
 date last changed
 20170101 08:01:16
@inproceedings{627189028a174700887a3cf62f717944, 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}, booktitle = {Algorithms and data structures : 7th International Workshop, WADS 2001, Providence, RI, USA, August 810, 2001 : proceedings}, isbn = {3540424237}, language = {eng}, pages = {258263}, publisher = {Springer}, title = {Fast Boolean matrix multiplication for highly clustered data}, url = {http://dx.doi.org/10.1007/3540446346_24}, volume = {LNCS 2125}, year = {2001}, }