Paper Info
Title
DSMR: A Parallel Algorithm for Single-Source Shortest Path Problem.
Abstract
The Single Source Shortest Path (SSSP) problem consists in finding the shortest paths from a vertex (the source vertex) to all other vertices in a graph. SSSP has numerous applications. For some algorithms and applications, it is useful to solve the SSSP problem in parallel. This is the case of Betweenness Centrality which solves the SSSP problem for multiple source vertices in large graphs. In this paper, we introduce the Dijkstra Strip Mined Relaxation (DSMR) algorithm, an efficient parallel SSSP algorithm for shared and distributed-memory systems. We also introduce a set of preprocessing optimization techniques that significantly reduce the communication overhead without increasing the total amount of work dramatically. Our results show that, DSMR is faster than the best previous algorithm, parallel Δ-Stepping, by up-to 7.38×.
Year
Venue
Field
2016
ICS
Graph,Shortest path problem,Vertex (geometry),Computer science,Parallel algorithm,Parallel computing,Real-time operating system,Betweenness centrality,Preprocessor,Dijkstra's algorithm
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
6
Name
Order
Citations
PageRank
Saeed Maleki1746.81
Donald Nguyen241917.94
Andrew Lenharth345619.94
María Jesús Garzarán441134.13
David A. Padua54540590.45
Keshav Pingali63056256.64