Parallel shortest paths using radius stepping
© 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...
Saved in:
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Conference or Workshop Item |
Published: |
2018
|
Subjects: | |
Online Access: | https://repository.li.mahidol.ac.th/handle/123456789/43504 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Mahidol University |
id |
th-mahidol.43504 |
---|---|
record_format |
dspace |
spelling |
th-mahidol.435042019-03-14T15:04:34Z Parallel shortest paths using radius stepping Guy E. Blelloch Yan Gu Yihan Sun Kanat Tangwongsan Carnegie Mellon University Mahidol University Computer Science Mathematics © 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. 2018-12-11T02:38:47Z 2019-03-14T08:04:34Z 2018-12-11T02:38:47Z 2019-03-14T08:04:34Z 2016-07-11 Conference Paper Annual ACM Symposium on Parallelism in Algorithms and Architectures. Vol.11-13-July-2016, (2016), 443-454 10.1145/2935764.2935765 2-s2.0-84979736771 https://repository.li.mahidol.ac.th/handle/123456789/43504 Mahidol University SCOPUS https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84979736771&origin=inward |
institution |
Mahidol University |
building |
Mahidol University Library |
continent |
Asia |
country |
Thailand Thailand |
content_provider |
Mahidol University Library |
collection |
Mahidol University Institutional Repository |
topic |
Computer Science Mathematics |
spellingShingle |
Computer Science Mathematics Guy E. Blelloch Yan Gu Yihan Sun Kanat Tangwongsan Parallel shortest paths using radius stepping |
description |
© 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. |
author2 |
Carnegie Mellon University |
author_facet |
Carnegie Mellon University Guy E. Blelloch Yan Gu Yihan Sun Kanat Tangwongsan |
format |
Conference or Workshop Item |
author |
Guy E. Blelloch Yan Gu Yihan Sun Kanat Tangwongsan |
author_sort |
Guy E. Blelloch |
title |
Parallel shortest paths using radius stepping |
title_short |
Parallel shortest paths using radius stepping |
title_full |
Parallel shortest paths using radius stepping |
title_fullStr |
Parallel shortest paths using radius stepping |
title_full_unstemmed |
Parallel shortest paths using radius stepping |
title_sort |
parallel shortest paths using radius stepping |
publishDate |
2018 |
url |
https://repository.li.mahidol.ac.th/handle/123456789/43504 |
_version_ |
1763495643222900736 |