𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Using Selective Path-Doubling for Parallel Shortest-Path Computations

✍ Scribed by Edith Cohen

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
291 KB
Volume
22
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

We 1 consider parallel shortest-paths computations in weighted undirected graphs Ž . < < < < Ž 3 . Gs V, E , where n s V and m s E . The standard O n work path-doubling Ž . Ž . Floyd-Warshall algorithm consists of O log n phases, where in each phase, for Ž . 3 every triplet of vertices u , u , u g V , the distance between u and u is 1 2 3 1 3 updated to be no more than the sum of the previous-phase distances between Ä 4 Ä 4 Ž . u,u and u , u . We introduce a new N N C C algorithm that for ␦ s o n , 1 2 2 3 2 ˜2 Ž . Ž . considers only O n␦ triplets. Our algorithm performs O n␦ work and aug-˜Ž . ments E with O n␦ new weighted edges such that between every pair of vertices, Ž . Ž . Ž there exists a minimum weight path of size number of edges O nr␦ where ˜Ž . Ž .. O f ' O f polylog n . To compute shortest-paths, we apply to the augmented ˜Ž . graph algorithms that are efficient for small-size shortest paths. We obtain an O t ˜2 3 2

Ž< < . time O S n q n rt work deterministic PRAM algorithm for computing short-< < est-paths from S sources to all other vertices, where t F n is a parameter. When the ratio of the largest edge weight and the smallest edge weight is n O Žpolylog n. , the algorithm computes shortest paths. When weights are arbitrary, it computes paths within a factor of 1 q n y⍀ Žpolylog n. of shortest.

📜 SIMILAR VOLUMES

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

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 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