A Fast Implementation of Minimum Spanning Tree Method and Applying it to Kruskal’s and Prim’s Algorithms
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.
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
The SJCMS holds the rights of all the published papers. Authors are required to transfer copyrights to journal to make sure that the paper is solely published in SJCMS, however, authors and readers can freely read, download, copy, distribute, print, search, or link to the full texts of its articles and to use them for any other lawful purpose.
The SJCMS is licensed under Creative Commons Attribution-NonCommercial 4.0 International License.