Fast Boolean matrix multiplication for highly clustered data
(2001) 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 first row having values different 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:
https://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
- host publication
- 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)
- date added to LUP
- 2016-04-04 11:03:39
- date last changed
- 2025-04-04 14:23:28
@inproceedings{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 first row having values different 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 8-10, 2001 : proceedings}}, isbn = {{3540424237}}, language = {{eng}}, pages = {{258--263}}, publisher = {{Springer}}, title = {{Fast Boolean matrix multiplication for highly clustered data}}, url = {{https://lup.lub.lu.se/search/files/5685192/623754.pdf}}, doi = {{10.1007/3-540-44634-6_24}}, volume = {{LNCS 2125}}, year = {{2001}}, }