A parallel randomized approximation scheme for shortest paths

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. It has application, e.g., in approximate solution of multicommodity flow problems with unit capacities. We also show how to adapt the algorithm to perform better for planar graphs.