✦ LIBER ✦

A Randomized Parallel Algorithm for Single-Source Shortest Paths

✍ Scribed by Philip N Klein; Sairam Subramanian

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 179 KB
Volume: 25
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1997.0888

No coin nor oath required. For personal study only.

✦ Synopsis

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 based on the technique used by Ullman and Yannakakis in a parallel algorithm for breadth-first search.

📜 SIMILAR VOLUMES

A Simple Parallel Algorithm for the Sing

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

✍ Jesper L. Träff; Christos D. Zaroliagis 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 216 KB

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

Termination Detection for Parallel Short

Termination Detection for Parallel Shortest Path Algorithms

✍ Michelle R Hribar; Valerie E Taylor; David E Boyce 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 322 KB

Shortest path computation is required by a large number of applications such as VLSI, transportation, and communication networks. These applications, which are often very complex and have sparse networks, generally use parallel labeling shortest path algorithms. Such algorithms, when implemented on

Parallel Algorithm for Shortest Pairs of

Parallel Algorithm for Shortest Pairs of Edge-Disjoint Paths

✍ S. Banerjee; R.K. Ghosh; A.P.K. Reddy 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 241 KB

method a solution for MSP can be found within the same time bound. The problem of finding all pairs of shortest paths in a directed graph with nonnegative edge weights can be solved in O(log 2 n) time using n 3 /log n processors on a CREW PRAM [7]. Therefore, SSP can be solved within the same resou

Efficient truthful mechanisms for the si

Efficient truthful mechanisms for the single-source shortest paths tree problem

✍ L. Gualà; G. Proietti 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB

Approximation algorithms for some k-sour

Approximation algorithms for some k-source shortest paths spanning tree problems

✍ Yen Hung Chen; Bang Ye Wu; Chuan Yi Tang 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 206 KB

A Randomized Parallel Algorithm for Plan

A Randomized Parallel Algorithm for Planar Graph Isomorphism

✍ Hillel Gazit; John H Reif 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 223 KB

We present a parallel randomized algorithm running on a CRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph Ž Ž 2 . 1 q ⑀ which can be computed by known algorithms in O log n time with