CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

A Study of Different Parallel Implementations of Single Source Shortest Path Algorithms

by Dhirendra Pratap Singh, Nilay Khare
journal cover thumbnail

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

@article{ 10.5120/8603-2371,
author = { Dhirendra Pratap Singh, Nilay Khare },
title = { A Study of Different Parallel Implementations of Single Source Shortest Path Algorithms },
journal = { International Journal of Computer Applications },
issue_date = { September 2012 },
volume = { 54 },
number = { 10 },
month = { September },
year = { 2012 },
issn = { 0975-8887 },
pages = { 26-30 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume54/number10/8603-2371/ },
doi = { 10.5120/8603-2371 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:55:19.966673+05:30
%A Dhirendra Pratap Singh
%A Nilay Khare
%T A Study of Different Parallel Implementations of Single Source Shortest Path Algorithms
%J International Journal of Computer Applications
%@ 0975-8887
%V 54
%N 10
%P 26-30
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
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
  1. A. Crauser, K. Mehlhom, U. Meyer and P. Sanders, "A parallelization of dijkstra's shortest path algorithm", LNCS 1450, pp. 722-731, 1998.
  2. E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik 1, 269–271, 1959.
  3. 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.
  4. G. Brodal, J. Traff and C. D. Zarolingis, "A parallel priority data structure with applications", IEEE, pp. 689-693, 1997.
  5. 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.
  6. M. Papaefthymiou and J. Rodrigue, "Implementing parallel shortest-paths algorithms", DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 59-68, 1994.
  7. Pedro J. Martin, Roberto Torres and Antonio gavilanes, "CUDA Solutions for the SSSP problem", LNCS 5544, pp. 904-913, 2009.
  8. U. Meyer and P. Sanders, "?-stepping: a parallelizable shortest path algorithm", Journal of Algorithms 49, pp. 114-152, 2003.
  9. 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.
  10. R. E. Bellman, "On a routing problem", Quarterly of Applied Mathematics, 16: 87-90, 1958.
  11. L. R. Ford Jr. , and D. R. Fulkerson, "Flows in Network", Princeton University Press, 1962.
  12. M. Papaefthymiou and J. Rodrigue, "Implementing parallel shortest-paths algorithms", DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 59-68, 1994.
  13. Y. Tang, Y. Zhang and H. Chen, "A parallel shortest path algorithm based on graph-partitioning and iterative correcting", IEEE, pp. 155-161, 2008.
  14. A. Fetterer and S. Shekhar, "A performance analysis of hierarchical shortest path algorithms", IEEE, pp. 84-93, 1997.
  15. 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

Computer Science
Information Sciences

Keywords

Parallel shortest path algorithm Parallel algorithm Graph algorithm Dijkstra's algorithm

Powered by PhDFocusTM