Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

An improved bound on Boolean matrix multiplication for highly clustered data

Författare

Summary, in English

We consider the problem of computing the product of two n x n Boolean matrices A and B. For two 0 - I strings s = s(1)s(2) .... s(m) and u = u(1)u(2) ... u(m), an extended Hamming distance, eh(s, u), between the strings, is defined by a recursive equation eh(s, u) = eh(s(l+1) ... s(m), u(l+1) ... u(m)) + (s(1) + u(1) mod 2), where l is the maximum number, s.t., s(j) = s, and u(j) = u(1) for j = For any n x n Boolean matrix C, let GC be a complete weighted graph on the rows of C, where the weight of an edge between two rows is equal to its extended Hamming distance. Next, let MWT(C) be the weight of a minimum weight spanning, tree of GC. WE! show that the product of A and B as well as the so called witnesses of the product can be computed in time (O) over bar (n(n + min{MWT(A), MWT(B-t)}))(1). Since the extended Hamming distance between two strings never exceeds the standard Hamming distance between them, our result subsumes an earlier similar result on the Boolean matrix product in terms of the Hamming distance due to Bjorklund and Lingas [4]. We also observe that min{MWT(A),MWT(B-t)} = O(min{r(A),r(B)}), where r(A) and r(B) reflect the minimum number of rectangles required to cover ls in A and B, respectively. Hence, our result also generalizes the recent upper bound on the Boolean matrix product in terms of r(A) and r(B), due to Lingas [12].

Avdelning/ar

  • Computer Science

Publiceringsår

2003

Språk

Engelska

Sidor

329-339

Publikation/Tidskrift/Serie

Lecture Notes in Computer Science

Volym

2748

Dokumenttyp

Konferensbidrag

Förlag

Springer

Ämne

  • Computer Science

Conference name

8th International Workshop, WADS 2003

Conference date

2003-07-30 - 2003-08-01

Conference place

Ottawa, Ontario, Canada

Status

Published

Projekt

  • VR 2002-4049

ISBN/ISSN/Övrigt

  • ISSN: 0302-9743
  • ISSN: 1611-3349
  • ISBN: 978-3-540-40545-0