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

Performance Analysis of Parallel Speedup Techniques for Shortest Path Queries in Networks of Random and Planar Types

by R.kalpana, P.thambidurai
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 47 - Number 24
Year of Publication: 2012
Authors: R.kalpana, P.thambidurai
10.5120/7506-0618

R.kalpana, P.thambidurai . Performance Analysis of Parallel Speedup Techniques for Shortest Path Queries in Networks of Random and Planar Types. International Journal of Computer Applications. 47, 24 ( June 2012), 29-35. DOI=10.5120/7506-0618

@article{ 10.5120/7506-0618,
author = { R.kalpana, P.thambidurai },
title = { Performance Analysis of Parallel Speedup Techniques for Shortest Path Queries in Networks of Random and Planar Types },
journal = { International Journal of Computer Applications },
issue_date = { June 2012 },
volume = { 47 },
number = { 24 },
month = { June },
year = { 2012 },
issn = { 0975-8887 },
pages = { 29-35 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume47/number24/7506-0618/ },
doi = { 10.5120/7506-0618 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:42:43.988550+05:30
%A R.kalpana
%A P.thambidurai
%T Performance Analysis of Parallel Speedup Techniques for Shortest Path Queries in Networks of Random and Planar Types
%J International Journal of Computer Applications
%@ 0975-8887
%V 47
%N 24
%P 29-35
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The essential elements of any network application system uses shortest?path algorithm mostly for problems of network namely routing, viz. When seen in the light of the basic requirement of such a system, to provide high quality path identification or routing solutions fast, algorithms have to be efficient. There are many speedup techniques and combined speedup techniques available which find shortest path efficiently in networks. Also parallelization is incorporated in some of the speedup techniques, where the performance is monitored in multicore processors. This paper deals with comparison of parallelized speedup techniques with sequential version of the same and finding performance improvement achieved in parallelized speedup techniques with respect to runtime and number of vertices visited during shortest path computation. The techniques were tested in random and planar types of graph networks, which may be suitable for networks of the same type. Performance of parallelization has good impact of speedup in random graph type of networks(45% to 90% with respect to runtime and 25% to 830% with respect to vertices visited) than planar graph type of networks.

References
  1. DIJKSTRA, E. W. (1959) 'A note on two problems in connection with Graphs', In Numerische Mathematik, Vol. 1, Mathematisch Centrum, Amsterdam, The Netherlands, pp. 269–271.
  2. Frank Schulz, Dorothea Wagner, and Weihe, K. (2000) 'Dijkstra's algorithm on-line: An empirical case study from public railroad transport', ACM Journal of Experimental Algorithmics, Vol. 5.
  3. I. Phol. (1971) 'Bi-directional Search', In Machine Intelligence, volume 6, pp 124-140. Edinburgh Univ. Press, Edinburgh
  4. Andrew V. Goldberg and Chris Harrelson. (2005) 'Computing the Shortest Path: A* Search Meets Graph Theory', In Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms.
  5. Andrew V. Goldberg and Renato F. Wernecky. (2005) 'Computing Point-to-Point Shortest Paths from External Memory', In Proc. Of The Seventh Workshop on Algorithm Engineering and Experiments (ALENEX05).
  6. Frank Schulz, Dorothea Wagner, & Christos Zaroliagis. (2002) 'Using multi-level graphs for timetable information in railway systems', In Proc. 4th Workshop on Algorithm Engineering and Experiments. LNCS 2409, Springer-Verlag, New York. pp43- 59.
  7. Sanders, P. and Schultes. D. (2005) 'Highway hierarchies hasten exact shortest path queries', In the Proceedings European Symposium on Algorithms.
  8. Sanders, P. and Schultes, D. (2006) 'Engineering highway hierarchies', In the Proceedings of the 14th European Symposium on Algorithms. LNCS,vol. 4168. Springer, New York. Pp. 804–816.
  9. Schultes. D and Sanders. P. (2007) 'Dynamic highway-node routing', In Proceedings of the 6thWorkshop on Experimental and Efficient algorithms,LNCS. Springer, New York pp. 66–79.
  10. Martin Holzer, Frank Schulz and Dorothea Wagner. (2008) 'Engineering Multilevel Overlay Graphs for Shortest-Path Queries', ACM Journal of Experimental Algorithmics, Vol. 13, Article No. 2. 5, September.
  11. Dorothea Wagner and Thomas Willhalm. (2005)'Geometric Containers for Efficient Shortest-Path Computation', ACM Journal of Experimental Algorithmics, Vol. 10, Article No. 1. 3, pp. 1-30.
  12. Mohring, R. H. , Schilling, H. , Schutz, B. ,Wagner. D. , and Willhalm, T. (2006) 'Partitioning graphs to speed up Dijkstra's algorithm', ACM Journal of Experimental Algorithmics, Vol. 11, Article No. 2. 8, pp. 1-29.
  13. GUTMAN, R. J. (2004) 'Reach-based routing: A new approach to shortest path algorithms optimized for road networks', In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics.
  14. Dorothea Wagner and Thomas Willhalm. (2007) 'Speed-Up Techniques for Shortest-Path Computations', In Proc. STACS 2007, LNCS , Springer-Verlag, New York. pp43- 59.
  15. Holzer, M, Schulz. F, Wagner and Willhalm. T. (2006) 'Combining speed-up techniques for shortest-path computations', ACM Journal of Experimental Algorithmics, Vol. 10, Article No. 2. 5, pp. 1-18.
  16. Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, & Dorothea Wagner. (2010) 'Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm', ACM Journal of Experimental Algorithmics, Vol. 15, Article No. 3.
  17. The Advanced Computing Systems Association (2000) 'Amdahl's law & Parallel Speedup', http://www. usenix. org/publications/library/proceedings/als00/2000papers/papers/full_papers/brownrobert/brownrobert_html/node3. html
  18. Daniel Delling, Bastian Katz and Thomas Pajor, "Parallel Computation of Best Connections in Public Transportation Networks" , In: 24th International Parallel and Distributed Processing Symposium (IPDPS'10), pages 1-12. , IEEE Computer Society, 2010.
  19. R. C. Paige and C. P. Kruskal, "Parallel algorithms for shortest path problems," 1985, pp. 553–556.
  20. J. R. Driscoll, H. N. Gabow, R. Shrairman, and R. E. Tarjan, "Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation," Comm. ACM, vol. 31, no. 11, pp. 1343–1354, 1988.
  21. K. M. Chandy and J. Misra, "Distributed computation on graphs: Shortest path algorithms," Comm. ACM, vol. 25, no. 11, pp. 833–837, 1982.
  22. K. V. S. Ramarao and S. Venkatesan, "On finding and updating shortest paths distributively," J. Algorithms, vol. 13, pp. 235–257, 1992.
  23. Dominik Schultes, Johannes Singler, Peter Sanders. (2008)'Parallel Highway Node Routing', A Technical Report, Feburuary. algo2. iti. kit. edu/schultes/hwy/parallelHNR. pdf
  24. R. Kalpana, P. Thambidurai, Arvind Kumar, R. Parthasarathy, and Praful Ravi. (2010), 'Exploiting Parallelism in Bidirectional Dijkstra for Shortest-Path Computation', in the Proceedings of International conference on Computers, Communication and Intelligence at , Vellammal college of Engg. , & Tech. ,Madurai, India, pp. 351-356, July.
  25. R. Kalpana, P. Thambidurai,(2010), 'Optimization of Landmark preprocessing with Mulitcore Systems', Journal of Computing, Vol. 2, Issue. 8, pp. 102-108, August.
  26. R. Kalpana, P. Thambidurai (2011), 'Optimizing shortest path queries with parallelized Arc flags', in the Proceedings of IEEE International conference on Recent trends in Information Technology, MIT Campus,Anna University, Chennai, India, June.
  27. R. Kalpana, P. Thambidurai (2011), 'Parallelized Multilevel Arc Flags Improve Speedup In Shortest Path Queries', , in the Proceedings of the IEEE International Conference on Process Automation, Control and Computing, CIT, Coimbatore, July 2011.
  28. 'The OpenMP - API specification for parallel programming', available at http://www. openmp. org
  29. Algorithmic Solutions Software GmbH (1995) 'LEDA', available at http://www. algorithmic-solutions. com
Index Terms

Computer Science
Information Sciences

Keywords

Dijkstra's Algorithm Shortest Path Computation Speedup Techniques Parallel Speedup.

Powered by PhDFocusTM