The week's pick
Random Articles
Reseach Article
A Study of Different Parallel Implementations of Single Source Shortest Path Algorithms
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 54 - Number 10 |
| Year of Publication: 2012 |
| Authors: Dhirendra Pratap Singh, Nilay Khare |
10.5120/8603-2371
|
Dhirendra Pratap Singh, Nilay Khare . A Study of Different Parallel Implementations of Single Source Shortest Path Algorithms. International Journal of Computer Applications. 54, 10 ( September 2012), 26-30. DOI=10.5120/8603-2371
Abstract
We present a study of parallel implementations of single source shortest path (SSSP) algorithms. In the last three decades number of parallel SSSP algorithms have been developed and implemented on the different type of machines. We have divided some of these implementations into two groups, first are those where parallelization is achieved in the internal operations of sequential SSSP algorithm and second are where an actual graph is divided into sub-graphs, and serial SSSP algorithm executes parallel on separate processing units for each sub-graph. These parallel implementations have used PRAM, CRAY super-computer, dynamically reconfigurable processor and Graphics processing unit as platform to run them.
References
- A. Crauser, K. Mehlhom, U. Meyer and P. Sanders, "A parallelization of dijkstra's shortest path algorithm", LNCS 1450, pp. 722-731, 1998.
- E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik 1, 269–271, 1959.
- G. Brodal, J. Traff and C. D. Zarolingis, "A parallel priority queue with constant time operations", Journal of parallel and distributed computing 49, pp. 4-12, 1998.
- G. Brodal, J. Traff and C. D. Zarolingis, "A parallel priority data structure with applications", IEEE, pp. 689-693, 1997.
- J. R. Crobak, J. W. Berry, K. Madduri and D A. Bader, "Advanced shortest paths algorithms on a massively-multithreaded architecture", Parallel and Distributed Processing Symposium, 2007, IEEE, pp. 1-8, 2007.
- M. Papaefthymiou and J. Rodrigue, "Implementing parallel shortest-paths algorithms", DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 59-68, 1994.
- Pedro J. Martin, Roberto Torres and Antonio gavilanes, "CUDA Solutions for the SSSP problem", LNCS 5544, pp. 904-913, 2009.
- U. Meyer and P. Sanders, "?-stepping: a parallelizable shortest path algorithm", Journal of Algorithms 49, pp. 114-152, 2003.
- K. Madduri, D. Bader, J. Berry and J. Croba, " An experimental study of a parallel shortest path algorithm for solving large-scale graph instances", In workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, LA, January 2007.
- R. E. Bellman, "On a routing problem", Quarterly of Applied Mathematics, 16: 87-90, 1958.
- L. R. Ford Jr. , and D. R. Fulkerson, "Flows in Network", Princeton University Press, 1962.
- M. Papaefthymiou and J. Rodrigue, "Implementing parallel shortest-paths algorithms", DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 59-68, 1994.
- Y. Tang, Y. Zhang and H. Chen, "A parallel shortest path algorithm based on graph-partitioning and iterative correcting", IEEE, pp. 155-161, 2008.
- A. Fetterer and S. Shekhar, "A performance analysis of hierarchical shortest path algorithms", IEEE, pp. 84-93, 1997.
- H. Ishikawa, S. Shimizu, Y. Arakawa, N. Yamanaka and K. Shiba, "New parallel shortest path searching algorithm based on dynamically reconfigurable processor DAPDNA-2", IEEE, pp. 1997 – 2002, 2007.
Index Terms
Keywords