AN EFFICIENT PARALLEL ALGORITHM FOR SHORTEST PATHS IN PLANAR LAYERED DIGRAPHS

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, develo ping a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We p resent a first step in this direction by giving efficient parallel alg orithms for shortest paths in planar layered digraphs. We show that th ese graphs admit special kinds of separators called one-way separators which allow the paths in the graph to cross it only once. We use thes e separators to give divide-and-conquer solutions to the problem of fi nding the shortest paths between any two vertices. We first give a sim ple algorithm that works in the CREW model and computes the shortest p ath between any two vertices in an n-node planar layered digraph in ti me O(log(2) n) using n/log n processors. We then use results of Aggarw al and Park [1] and Atallah [4] to improve the time bound to O(log(2) n) in the CREW model and O(log n log log n) in the CREW model. The pro cessor bounds still remain as n/log n for the CREW model and n/log log n for the CRCW model.