An efficient parallel algorithm for shortest paths in planar layered digraphs |
| |
Authors: | Mishra P K |
| |
Institution: | Dept. of Applied Mathematics, Birla Institute of Technology, Mesra, Ranchi 835215, India. pkmishra@ieee.org |
| |
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. |
| |
Keywords: | |
本文献已被 维普 PubMed 等数据库收录! |
|