Title | ||
---|---|---|
DSMR: a shared and distributed memory algorithm for single-source shortest path problem. |
Abstract | ||
---|---|---|
The Single-Source Shortest Path (SSSP) problem is to find the shortest paths from a source vertex to all other vertices in a graph. In this paper, we introduce the Dijkstra Strip-Mined Relaxation (DSMR) algorithm, an efficient parallel SSSP algorithm for shared and distributed memory systems. Our results show that, DSMR is faster than parallel Δ-Stepping by a factor of up-to 1.66. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1145/2851141.2851183 | PPOPP |
Field | DocType | Volume |
Computer science,Theoretical computer science,Shortest Path Faster Algorithm,K shortest path routing,Distributed computing,Dijkstra's algorithm,Pathfinding,Vertex (geometry),Shortest path problem,Parallel computing,Algorithm,Distributed memory,Yen's algorithm | Conference | 51 |
Issue | ISSN | Citations |
8 | 0362-1340 | 0 |
PageRank | References | Authors |
0.34 | 2 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Saeed Maleki | 1 | 74 | 6.81 |
Donald Nguyen | 2 | 419 | 17.94 |
Andrew Lenharth | 3 | 456 | 19.94 |
María Jesús Garzarán | 4 | 411 | 34.13 |
David A. Padua | 5 | 4540 | 590.45 |
Keshav Pingali | 6 | 3056 | 256.64 |