|
|
Journal of Zhejiang University SCIENCE A
ISSN 1673-565X(Print), 1862-1775(Online), Monthly
2004 Vol.5 No.5 P.518-527
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 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.
Key words: Parallel algorithms, Shortest paths, Planar layered digraphs
References:
Open peer comments: Debate/Discuss/Question/Opinion
<1>
DOI:
10.1631/jzus.2004.0518
CLC number:
O29
Download Full Text:
Downloaded:
2418
Clicked:
4491
Cited:
0
On-line Access:
Received:
2003-07-21
Revision Accepted:
2003-11-04
Crosschecked: