Paper Info
Title
Witnesses for Boolean matrix multiplication and for shortest paths
Abstract
The subcubic (O(n/sup w/) for w(3) algorithms to multiply Boolean matrices do not provide the witnesses; namely, they compute C=A.B but if C/sub ij/=1 they do not find an index k (a witness) such that A/sub ik/=B/sub kj/=1. The authors design a deterministic algorithm for computing the matrix of witnesses that runs in O(n/sup w/) time, where here O(n/sup w/) denotes O(n/sup w/(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 v/sub i/ to v/sub j/ is an index k such that v/sub k/ 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(n/sup w/) 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.
Year
DOI
Venue
1992
10.1109/SFCS.1992.267748
Pittsburgh, PA
Keywords
Field
DocType
sub ij,denotes o,boolean matrix multiplication,shortest path,shortest paths algorithm,pairs shortest paths problem,sup w,shortest distance,sup o,subcubic method,index k,indexation,random variables,graph theory,shortest path algorithm,shortest path problem,all pairs shortest path,computational geometry,mathematics,matrix multiplication,algorithm design and analysis,computer science,transitive closure,deterministic algorithm,computational complexity,boolean algebra
Graph theory,Discrete mathematics,Binary logarithm,Combinatorics,Shortest path problem,Vertex (geometry),Matrix (mathematics),Boolean algebra,Deterministic algorithm,Transitive closure,Mathematics
Conference
ISBN
Citations 
PageRank 
0-8186-2900-2
39
5.05
References 
Authors
4
4
Name
Order
Citations
PageRank
Noga Alon1104681688.16
Zvi Galil236341426.98
O. Margalit3415.75
Moni Naor4129481311.21