Abstract
In dynamic networks, where continuous topological changes are prevalent, it becomes paramount to find and update different graph properties without the computational burden of recalculating from the ground up. However finding or updating a multi-objective shortest path (MOSP) in such a network is challenging, as it involves simultaneously optimizing multiple (conflicting) objectives. In light of this, our paper focuses on shortest path search and proposes parallel algorithms tailored specifically for large incremental graphs. We first present an efficient algorithm that updates the single-objective shortest path (SOSP) whenever a new set of edges are introduced. Leveraging this SOSP update algorithm, we also devise a novel heuristic approach to adaptively update a MOSP in large networks. Empirical evaluations on both real and synthetic incremental networks with shared memory implementations attest to the scalability and efficacy of the proposed algorithms.
Recommended Citation
A. Khanda et al., "A Parallel Algorithm For Updating A Multi-objective Shortest Path In Large Dynamic Networks," ACM International Conference Proceeding Series, pp. 739 - 746, Association for Computing Machinery, Nov 2023.
The definitive version is available at https://doi.org/10.1145/3624062.3625134
Department(s)
Computer Science
Keywords and Phrases
dynamic graph; parallel algorithm; shortest path
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2023 Association for Computing Machinery, All rights reserved.
Publication Date
12 Nov 2023
Comments
National Science Foundation, Grant OAC-2104078