Fast Boolean matrix multiplication for highly clustered data

Andreas Björklund, Andrzej Lingas

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingpeer-review

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
Original languageEnglish
Title of host publicationAlgorithms and data structures : 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001 : proceedings
PublisherSpringer
Pages258-263
VolumeLNCS 2125
ISBN (Print)3540424237
DOIs
Publication statusPublished - 2001

Publication series

Name
VolumeLNCS 2125

Subject classification (UKÄ)

  • Computer Science

Fingerprint

Dive into the research topics of 'Fast Boolean matrix multiplication for highly clustered data'. Together they form a unique fingerprint.

Cite this