𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs

✍ Scribed by Jesper L. Träff; Christos D. Zaroliagis

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
216 KB
Volume
60
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

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((n 2= +n 1&= ) log n) time, performing O(n 1+= 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.

📜 SIMILAR VOLUMES

A Randomized Parallel Algorithm for Sing
A Randomized Parallel Algorithm for Single-Source Shortest Paths
✍ Philip N Klein; Sairam Subramanian 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 179 KB

We give a randomized parallel algorithm for computing single-source shortest paths in weighted digraphs. We show that the exact shortest-path problem can be efficiently reduced to solving a series of approximate shortest-path subproblems. Our algorithm for the approximate shortest-path problem is ba

A simpleO(n2) algorithm for the all-pair
A simpleO(n2) algorithm for the all-pairs shortest path problem on an interval graph
✍ Mirchandani, Prakash 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB 👁 3 views

Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O(n') algorithm for solving the all-pairs shortest path problem on graph G . A recent algorithm for this problem has the same time-complexity but is fairly complicated to describe. However, our a