link.springer.com

Parallelization of Minimum Spanning Tree Algorithms Using Distributed Memory Architectures

  • ️Wed Jan 01 2014

Abstract

Finding a minimum spanning tree of a graph is a well known problem in graph theory with many practical applications. We study serial variants of Prim’s and Kruskal’s algorithm and present their parallelization targeting message passing parallel machine with distributed memory. We consider large graphs that can not fit into memory of one process. Experimental results show that Prim’s algorithm is a good choice for dense graphs while Kruskal’s algorithm is better for sparse ones. Poor scalability of Prim’s algorithm comes from its high communication cost while Kruskal’s algorithm showed much better scaling to larger number of processes.

Similar content being viewed by others

References

  1. H. Ahrabian, A. Nowzari-Dalini, Parallel algorithms for minimum spanning tree problem. Int. J. Comput. Math. 79(4), 441–448 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  2. D.A. Bader, G. Cong, Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs. J. Parallel Distrib. Comput. 66(11), 1366–1378 (2006)

    Article  MATH  Google Scholar 

  3. O. Boruvka, O Jistém Problému Minimálnm (about a certain minimal problem) (in Czech, German summary). Práce Mor. Prrodoved. Spol. v Brne III, vol. 3 (1926)

    Google Scholar 

  4. S. Chung, A. Condon, Parallel implementation of borvka’s minimum spanning tree algorithm. in Proceedings of the 10th International Parallel Processing Symposium, IPPS ‘96 (IEEE Computer Society, Washington, DC, 1996), pp. 302–308

    Google Scholar 

  5. T.H. Cormen, C. Stein, R.L. Rivest, C.E. Leiserson, Introduction to Algorithms, 2nd edn. (McGraw-Hill Higher Education, Boston, 2001)

    MATH  Google Scholar 

  6. M. Curtis-Maury, X. Ding, C.D. Antonopoulos, D.S. Nikolopoulos, An Evaluation of Openmp on Current and Emerging Multithreaded/Multicore Processors, ed. by M.S. Mueller, B.M. Chapman, B.R. Supinski, A.D. Malony, M. Voss. OpenMP Shared Memory Parallel Programming, vol 4315 (Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2008), pp. 133–144

    Google Scholar 

  7. F. Dehne, S. Gtz, Practical Parallel Algorithms for Minimum Spanning Trees, in Workshop on Advances in Parallel and Distributed Systems (1998), pp. 366–371

    Google Scholar 

  8. N. Deo, Y.B. Yoo, Parallel algorithms for the minimum spanning tree problem, in Proceedings of the International Conference on Parallel Processing (1981), pp. 188–189

    Google Scholar 

  9. Z. Galil, G.F. Italiano, Data structures and algorithms for disjoint set union problems. ACM Comput. Surv. 23(3), 319–344 (1991)

    Article  Google Scholar 

  10. R.G. Gallager, P.A. Humblet, P.M. Spira, A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5(1), 66–77 (1983)

    Article  MATH  Google Scholar 

  11. E. Gonina, L.V. Kale, Parallel prim’s algorithm on dense graphs with a novel extension, in PPL Technical Report, Oct 2007

    Google Scholar 

  12. R.L. Graham, P. Hell, On the history of the minimum spanning tree problem. IEEE Ann. Hist. Comput. 7(1), 43–57 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  13. A. Grama, G. Karypis, V. Kumar, A. Gupta, Introduction to Parallel Computing, 2nd edn. (Addison Wesley, Reading, 2003)

    Google Scholar 

  14. W. Guang-rong, G. Nai-jie, An efficient parallel minimum spanning tree algorithm on message passing parallel machine. J. Softw. 11(7), 889–898 (2000)

    Google Scholar 

  15. M. Harris, Optimizing parallel reduction in CUDA. CUDA tips and tricks

    Google Scholar 

  16. M. Jin, J.W. Baker, Two graph algorithms on an associative computing model, in Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA 2007, vol 1, Las Vegas, Nevada, 25–28 June 2007, pp. 271–277

    Google Scholar 

  17. I. Katriel, P. Sanders, J.L. Trff, J.L. Tra, A practical minimum spanning tree algorithm using the cycle property, in 11th European Symposium on Algorithms (ESA), vol. 2832 in LNCS (Springer, New York, 2003), pp. 679–690

    Google Scholar 

  18. J.B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48–50 (1956)

    Article  MATH  MathSciNet  Google Scholar 

  19. V. Lončar, S. Škrbić, A. Balaž, Distributed memory parallel algorithms for minimum spanning trees, in Lecture Notes in Engineering and Computer Science: Proceedings of the World Congress on Engineering 2013, WCE 2013, London, 3–5 July 2013, pp. 1271–1275

    Google Scholar 

  20. Nvidia, Nvidia tesla GPU accelerators. Nvidia Tesla Product Datasheet (2012)

    Google Scholar 

  21. V. Osipov, P. Sanders, J. Singler, The filter-kruskal minimum spanning tree algorithm, in ALENEX’09 (2009), pp. 52–61

    Google Scholar 

  22. D.-Z. Pan, Z.-B. Liu, X.-F. Ding, Q. Zheng, The application of union-find sets in kruskal algorithm, in Proceedings of the 2009 International Conference on Artificial Intelligence and Computational Intelligence (AICI ‘09), vol 2 (IEEE Computer Society, Washington, DC, 2009), pp. 159–162

    Google Scholar 

  23. R.C. Prim, Shortest connection networks and some generalizations. Bell Syst. Technol. J. 36, 1389–1401 (1957)

    Article  Google Scholar 

  24. R. Setia, A. Nedunchezhian, S. Balachandran, A new parallel algorithm for minimum spanning tree problem, in Proceedings of the International Conference on High Performance Computing (HiPC) (2009), pp. 1–5

    Google Scholar 

  25. S. Škrbić, Scientific Computing Seminar (2013)

    Google Scholar 

Download references

Acknowledgements

Authors are partially supported by Ministry of Education, Science, and Technological Development of the Republic of Serbia, through projects no. ON174023: “Intelligent techniques and their integration into wide-spectrum decision support”, and ON171017: “Modeling and numerical simulations of complex many-body systems”, as well as European Commission through FP7 projects PRACE-2IP and PRACE-3IP.

Author information

Authors and Affiliations

  1. Faculty of Science, University of Novi Sad, Trg Dositeja Obradovica 4, Novi Sad, Serbia

    Vladimir Lončar & Srdjan Škrbić

  2. Scientific Computing Laboratory, Institute of Physics Belgrade, University of Belgrade, Pregrevica 118, Belgrade, Serbia

    Antun Balaž

Authors

  1. Vladimir Lončar

    You can also search for this author in PubMed Google Scholar

  2. Srdjan Škrbić

    You can also search for this author in PubMed Google Scholar

  3. Antun Balaž

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Srdjan Škrbić .

Editor information

Editors and Affiliations

  1. Department of Multimedia Engineering, College of Engineering, Mokpo National University, Mokpo, Jeonnam, Korea, Republic of (South Korea)

    Gi-Chul Yang

  2. Unit 1, 1/F IAENG Secretariat, International Association of Engine, Hong Kong, Hong Kong SAR

    Sio-Iong Ao

  3. Department of Applied Mathematics and Computing, Cranfield University, Cranfield, Bedfordshire, United Kingdom

    Len Gelman

© 2014 Springer Science+Business Media Dordrecht

About this paper

Cite this paper

Lončar, V., Škrbić, S., Balaž, A. (2014). Parallelization of Minimum Spanning Tree Algorithms Using Distributed Memory Architectures. In: Yang, GC., Ao, SI., Gelman, L. (eds) Transactions on Engineering Technologies. Springer, Dordrecht. https://doi.org/10.1007/978-94-017-8832-8_39

Download citation

  • DOI: https://doi.org/10.1007/978-94-017-8832-8_39

  • Published: 27 April 2014

  • Publisher Name: Springer, Dordrecht

  • Print ISBN: 978-94-017-8831-1

  • Online ISBN: 978-94-017-8832-8

  • eBook Packages: EngineeringEngineering (R0)

Publish with us