Sökning: id:"swepub:oai:lup.lub.lu.se:62718902-8a17-4700-887a-3cf62f717944" >
Fast Boolean matrix...
Fast Boolean matrix multiplication for highly clustered data
-
- Björklund, Andreas (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
- Lingas, Andrzej (författare)
- Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science
-
(creator_code:org_t)
- 2001-08-02
- 2001
- Engelska.
-
Ingår i: Algorithms and data structures : 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001 : proceedings. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 3540424237 ; LNCS 2125, s. 258-263
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas