Tech Report CS-91-56
A Parallel Randomized Approximation Scheme for Shortest Paths
Philip N. Klein
August 1991
Abstract:
We give a randomized parallel algorithm for approximate shortest-path computation in an undirected weighted graph. The algorithm is based on a technique used by Ullman and Yannakakis in a parallel algorithm for breadth-first search.
(complete text in pdf)