Witnesses for Boolean matrix multiplication and for shortest paths

Noga Alon, Zvi Galil, Oded Margalit, Moni Naor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

41 Scopus citations

Abstract

The subcubic (O(nw) for w(3) algorithms to multiply Boolean matrices do not provide the witnesses; namely, they compute C=A.B but if Cij=1 they do not find an index k (a witness) such that Aik=Bkj=1. The authors design a deterministic algorithm for computing the matrix of witnesses that runs in O(nw) time, where here O(nw) denotes O(nw(log n)/sup O(1)/). The subcubic methods to compute the shortest distances between all pairs of vertices also do not provide for witnesses; namely they compute the shortest distances but do not generate information for computing quickly the paths themselves. A witness for a shortest path from vi to vj is an index k such that vk is the first vertex on such a path. They describe subcubic methods to compute such witnesses for several versions of the all pairs shortest paths problem. As a result, they derive shortest paths algorithms that provide characterization of the shortest paths in addition to the shortest distances in the same time (up to a polylogarithmic factor) needed for computing the distances; namely O(n/sup (3+w)/2/) time in the directed case and O(nw) time in the undirected case. They also design an algorithm that computes witnesses for the transitive closure in the same time needed to compute witnesses for Boolean matrix multiplication.

Original languageEnglish (US)
Title of host publicationProceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
PublisherIEEE Computer Society
Pages417-426
Number of pages10
ISBN (Electronic)0818629002
DOIs
StatePublished - Jan 1 1992
Externally publishedYes
Event33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 - Pittsburgh, United States
Duration: Oct 24 1992Oct 27 1992

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume1992-October
ISSN (Print)0272-5428

Conference

Conference33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
CountryUnited States
CityPittsburgh
Period10/24/9210/27/92

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Cite this

Alon, N., Galil, Z., Margalit, O., & Naor, M. (1992). Witnesses for Boolean matrix multiplication and for shortest paths. In Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 (pp. 417-426). [267748] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 1992-October). IEEE Computer Society. https://doi.org/10.1109/SFCS.1992.267748