Tech Report CS-92-15

A Divide-and-Conquer Approach to Shortest Paths in Planar Layered Digraphs

S. Sairam, Roberto Tamassia, and Jeffery Scott Vitter

March 1992

Abstract:

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We present a first step in this direction by showing that for an $n$-node planar layered digraph with nonnegative edge-weights the shortest path between any two vertices can be computed in $O(\log^3n)$ time with $n$ processors in a CREW PRAM. A CRCW version of our algorithm runs in time $O(\log^2 n \log \log )$ and uses~$n\log n/\log \log n$ processors. Our results make use of the existence of special kinds of separators in planar layered digraphs, called one-way separators, to implement a divide-and-conquer solution.

(complete text in pdf or gzipped postscript)