TY - GEN

T1 - Witnesses for Boolean matrix multiplication and for shortest paths

AU - Alon, Noga

AU - Galil, Zvi

AU - Margalit, Oded

AU - Naor, Moni

N1 - Funding Information:
Research supported in part by a United states Israel BSF Grant. Work partially supported by NSF Grant CCR-9014605.

PY - 1992

Y1 - 1992

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84969333008&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84969333008&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1992.267748

DO - 10.1109/SFCS.1992.267748

M3 - Conference contribution

AN - SCOPUS:84969333008

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 417

EP - 426

BT - Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992

PB - IEEE Computer Society

T2 - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992

Y2 - 24 October 1992 through 27 October 1992

ER -