An efficient parallel algorithm for shortest paths in planar layered digraphs

摘要

This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log~3n) time with n processors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way s eparator, which has the property that any directed path can be crossed only once.