Publication: Parallel shortest paths using radius stepping
1
Issued Date
2016-07-11
Resource Type
Other identifier(s)
2-s2.0-84979736771
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
Annual ACM Symposium on Parallelism in Algorithms and Architectures. Vol.11-13-July-2016, (2016), 443-454
Suggested Citation
Guy E. Blelloch, Yan Gu, Yihan Sun, Kanat Tangwongsan Parallel shortest paths using radius stepping. Annual ACM Symposium on Parallelism in Algorithms and Architectures. Vol.11-13-July-2016, (2016), 443-454. doi:10.1145/2935764.2935765 Retrieved from: https://repository.li.mahidol.ac.th/handle/123456789/43504
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
Parallel shortest paths using radius stepping
Author(s)
Other Contributor(s)
Abstract
© 2016 ACM. The single-source shortest path problem (SSSP) with nonnegative edge weights is notoriously difficult to solve efficiently in parallel-it is one of the graph problems said to suffer from the transitive-closure bottleneck. Yet, in practice, the Δ-stepping algorithm of Meyer and Sanders (J. Algorithms, 2003) often works efficiently but has no known theoretical bounds on general graphs. The algorithm takes a sequence of steps, each increasing the radius by a user-specified value Δ. Each step settles the vertices in its annulus but can take θ(n) substeps, each requiring θ(m) work (n vertices and m edges). Building on the success of Δ-stepping, this paper describes Radius-Stepping, an algorithm with one of the best-known tradeoffs between work and depth bounds for SSSP with nearly-linear (Õ(m)) work. The algorithm is a Δ-stepping-like algorithm but uses a variable instead of a fixed-size increase in radii, allowing us to prove a bound on the number of steps. In particular, by using what we define as a vertex k-radius, each step takes at most k + 2 substeps. Furthermore, we define a pk, ρ)-graph property and show that if an undirected graph has this property, then the number of steps can be bounded by Opn/ρ · log ρL), for a total of Opkn/ρ · logρL) substeps, each parallel. We describe how to preprocess a graph to have this property. Altogether, for an arbitrary input graph with n vertices and m edges, Radius-Stepping, after preprocessing, takes Oppm+nρ) logn) work and On/ρ-logn log p ρL)) depth per source. The preprocessing step takes p mlogn + nρ2) work and O pρ log ρ) depth, adding no more than Opnρ) edges.