## 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 ﬁrst row having values diﬀerent 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

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 ﬁrst row having values diﬀerent 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 language | English |
---|---|

Title of host publication | Algorithms and data structures : 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001 : proceedings |

Publisher | Springer |

Pages | 258-263 |

Volume | LNCS 2125 |

ISBN (Print) | 3540424237 |

DOIs | |

Publication status | Published - 2001 |

### Publication series

Name | |
---|---|

Volume | LNCS 2125 |

## Subject classification (UKÄ)

- Computer Science