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.

Authors

• Philip N. Klein
• Sairam Sairam

Keywords

No keywords are indexed for this paper.