Tech Report CS-91-56

A Parallel Randomized Approximation Scheme for Shortest Paths

Philip N. Klein

August 1991


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)