A Parallel Algorithm Template for Updating Single-Source Shortest Paths in Large-Scale Dynamic Networks
Abstract
The Single Source Shortest Path (SSSP) problem is a classic graph theory problem that arises frequently in various practical scenarios; hence, many parallel algorithms have been developed to solve it. However, these algorithms operate on static graphs, whereas many real-world problems are best modeled as dynamic networks, where the structure of the network changes with time. This gap between the dynamic graph modeling and the assumed static graph model in the conventional SSSP algorithms motivates this work. We present a novel parallel algorithmic framework for updating the SSSP in large-scale dynamic networks and implement it on the shared-memory and GPU platforms. The basic idea is to identify the portion of the network affected by the changes and update the information in a rooted tree data structure that stores the edges of the network that are most relevant to the analysis. Extensive experimental evaluations on real-world and synthetic networks demonstrate that our proposed parallel updating algorithm is scalable and, in most cases, requires significantly less execution time than the state-of-the-art recomputing-from-scratch algorithms.
Recommended Citation
A. Khanda et al., "A Parallel Algorithm Template for Updating Single-Source Shortest Paths in Large-Scale Dynamic Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 4, pp. 929 - 940, Institute of Electrical and Electronics Engineers (IEEE), Apr 2022.
The definitive version is available at https://doi.org/10.1109/TPDS.2021.3084096
Department(s)
Computer Science
Research Center/Lab(s)
Center for High Performance Computing Research
Keywords and Phrases
Complexity theory; Dynamic Networks; GPU Implementation; Graphics processing units; Heuristic algorithms; Multicore processing; Parallel algorithms; Shared-Memory Parallel Algorithm; Single Source Shortest Path (SSSP); Synchronization; Wireless sensor networks
International Standard Serial Number (ISSN)
1045-9219; 1558-2183
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2021 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
01 Apr 2022
Comments
Published online: 26 May 2021
This work is supported by the NSF OAC grants 1725755, 1725566, and 1725585 for the collaborative SANDY project. It is also supported in part by the NSF OAC grant 1919789.