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.
A Fast Implementation of Minimum Spanning Tree Method and Applying it to Kruskal’s and Prim’s Algorithms
2017-06-30
doi:10.30537/sjcms.v1i1.8
Sukkur IBA Journal of Computing and Mathematical Sciences; Vol 1 No 1 (2017): January - June 2017; 58-66 ; 2522-3003 ; 2520-0755 ; 10.30537/sjcms.v1i1
Article (Journal)
Electronic Resource
English
DDC: | 629 |
A MODIFICATION OF KRUSKAL'S ALGORITHM FOR SATELLITE IMAGE SEGMENTATION
British Library Conference Proceedings | 2016
|New Models of the Generalized Minimum Spanning Tree Problem
British Library Online Contents | 2004
|Radar Data Tracking Using Minimum Spanning Tree-Based Clustering Algorithm
British Library Conference Proceedings | 2011
|