Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

Fast Boolean matrix multiplication for highly clustered data

Publiceringsår: 2001
Språk: Engelska
Sidor: 258-263
Publikation/Tidskrift/Serie: Algorithms and data structures : 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001 : proceedings
Volym: LNCS 2125
Dokumenttyp: Konferensbidrag
Förlag: Springer


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)}))



  • Computer Science


  • ISBN: 3540424237

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen