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(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.
Mishra
P K
PK
Dept. of Applied Mathematics, Birla Institute of Technology, Mesra, Ranchi 835215, India. pkmishra@ieee.org