An efficient parallel algorithm for shortest paths in planar layered digraphs
Pramod Kumar Mishra · Journal of Zhejiang University. Science A · 2004
This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log3n) time with n processors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way separator, which has the property that any directed path can be crossed only once.