Polylog-time and near-linear work approximation scheme for undirected shortest paths
Author:
Open Access
- 1 January 2000
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 47 (1) , 132-166
Abstract
Shortest paths computations constitute one of the most fundamental network problems. Nonetheless, known parallel shortest-paths algorithms are generally inefficient: they perform significantly more work (product of time and processors) than their sequential counterparts. This gap, known in the literature as the “transitive closure bottleneck,” poses a long-standing open problem. Our main result is an O(mn ϵ 0 +s( m+n 1+ϵ 0 )) work polylog-time randomized algorithm that computes paths within (1 + O (1/polylog n ) of shortest from s source nodes to all other nodesin weighted undirected networks with n nodes and m edges (for any fixed ϵ 0 >0). This work bound nearly matches the Õ(sm) sequential time. In contrast, previous polylog-time algorithms required min {Õ(n 3 ), Õ(m 2 )} work (even when s =1), and previous near-linear work algorithms required near- O ( n ) time. We also present faster sequential algorithms that provide good approximate distances only between “distant” vertices: We obtain an O((m + sn)n ϵ0 time algorithm that computes paths of weight (1+ O (1/polylog n ) dist + O ( w max polylog n ), where dist is the corresponding distance and w max is the maximum edge weight. Our chief instrument, which is of independent interest, are efficient constructions of sparse hop sets . A ( d ,ϵ)-hop set of a network G =( V,E ) is a set E * of new weighted edges such that mimimum-weight d -edge paths in ( V, E, ∪ E* ) have weight within (1+ϵ) of the respective distances in G . We construct hop sets of size O (n 1+ϵ0 ) where ϵ= O (1/polylog n ) and d = O (polylog n ).Keywords
This publication has 8 references indexed in Scilit:
- Near-linear cost sequential and distributed constructions of sparse neighborhood covers2002
- Sparse partitions2002
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch tSIAM Journal on Computing, 1998
- Time-work tradeoffs for parallel algorithmsJournal of the ACM, 1997
- Using Selective Path-Doubling for Parallel Shortest-Path ComputationsJournal of Algorithms, 1997
- Efficient Parallel Shortest-Paths in Digraphs with a Separator DecompositionJournal of Algorithms, 1996
- A parallel randomized approximation scheme for shortest paths1992
- High-Probability Parallel Transitive-Closure AlgorithmsSIAM Journal on Computing, 1991