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

Full description

Saved in:
Bibliographic Details
Main Authors: Guy E. Blelloch, Yan Gu, Yihan Sun, Kanat Tangwongsan
Other Authors: Carnegie Mellon University
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