| Applied & Financial Mathematics |
|
|
|
|
| An efficient parallel algorithm for shortest paths in planar layered digraphs |
| MISHRA P.K. |
| Dept. of Applied Mathematics, Birla Institute of Technology, Mesra, Ranchi 835215, India |
|
|
|
Abstract This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log3n) time with nprocessors. 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.
|
|
Received: 21 July 2003
|
|
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
