title: An efficient parallel algorithm for shortest paths in planar layered digraphs.
abstract: 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.
authors.affiliation: Dept. of Applied Mathematics, Birla Institute of Technology, Mesra, Ranchi 835215, India. pkmishra@ieee.org
authors.forename: P K
authors.initials: PK
authors.lastname: Mishra