A Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs |
| |
| Affiliation: | 1. University of Texas Health Science Center Houston, School of Public Health, Michael and Susan Dell Center for Healthy Living, 7000 Fannin St. #2532, Houston, TX 77030, United States;2. Dept. of Epidemiology, Human Genetics and Environmental Sciences, University of Texas Health Science Center Houston, School of Public Health, Houston, TX 77030, United States;3. Dept. of Epidemiology, Human Genetics and Environmental Sciences, University of Texas Health Science Center Houston, School of Public Health, Austin Regional Campus, Michael and Susan Dell Center for Healthy Living, 1616 Guadalupe St, Suite 6.300, Austin, TX 78701, United States |
| |
| Abstract: | We present a simple parallel algorithm for the single-source shortest path problem in planar digraphs with nonnegative real edge weights. The algorithm runs on the EREW PRAM model of parallel computation in O((n2ε+n1−ε) log n) time, performing O(n1+ε log n) work for any 0<ε<1/2. The strength of the algorithm is its simplicity, making it easy to implement and presumable quite efficient in practice. The algorithm improves upon the work of all previous parallel algorithms. Our algorithm is based on a region decomposition of the input graph and uses a well-known parallel implementation of Dijkstra's algorithm. The logarithmic factor in both the work and the time can be eliminated by plugging in a less practical, sequential planar shortest path algorithm together with an improved parallel implementation of Dijkstra's algorithm. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
