A Fast Implementation of Minimum Spanning Tree Method and Applying it to Kruskal’s and Prim’s Algorithms

  • Badri Munier Department of Computer Science, Capital University of Science and Technology, Islamabad
  • Muhammad Aleem Department of Computer Science, Capital University of Science and Technology, Islamabad
  • Muhammad Arshad Islam Department of Computer Science, Capital University of Science and Technology, Islamabad
  • Muhammad Azhar Iqbal Department of Computer Science, Capital University of Science and Technology, Islamabad
  • Waqar Mehmood Department of Computer Science, COMSATS Institute of Information Technology, Wah Cantt

Abstract

In last decade, application developers attained improved performances by merely employing the machines based on higher-clocked processors. However, in 2003 multi-core processors emerged and eradicated the old processor manufacturing technology based on increasing processor’s clock frequencies. After emergence of new parallel processor architectures, serial applications must be re-engineered into parallel versions to exploit the computing power of the existing hardware. In this paper, we present an efficient parallel implementation of minimum spanning tree algorithm to take advantage of the computing power of multi-core machines. Computer network routing, civil infrastructure planning and cluster analysis are typically use-cases of spanning tree problem. The experimental results show that the proposed algorithm is scalable for different machine and graph sizes. The methodology is simple and can easily be implemented using different shared-memory parallel programming models.

Downloads

Download data is not yet available.
Published
2017-06-30
How to Cite
MUNIER, Badri et al. A Fast Implementation of Minimum Spanning Tree Method and Applying it to Kruskal’s and Prim’s Algorithms. Sukkur IBA Journal of Computing and Mathematical Sciences, [S.l.], v. 1, n. 1, p. 58-66, june 2017. ISSN 2522-3003. Available at: <http://journal.iba-suk.edu.pk:8089/SIBAJournals/index.php/sjcms/article/view/8>. Date accessed: 19 sep. 2020. doi: https://doi.org/10.30537/sjcms.v1i1.8.
Section
Research Articles