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.


    Access

    Download


    Export, share and cite



    Title :

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



    Publication date :

    2017-06-30


    Remarks:

    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



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English


    Classification :

    DDC:    629





    Neighborhood Hybrid Structure for Minimum Spanning Tree Problem

    Bahena, Beatriz Martinez / Cruz-Chavez, Marco Antonio / Diaz-Parra, Ocotlan et al. | IEEE | 2012


    A MODIFICATION OF KRUSKAL'S ALGORITHM FOR SATELLITE IMAGE SEGMENTATION

    Pelevin, Maksim / Tsvetkov, Misha | British Library Conference Proceedings | 2016


    New Models of the Generalized Minimum Spanning Tree Problem

    Pop, P. C. | British Library Online Contents | 2004


    Radar Data Tracking Using Minimum Spanning Tree-Based Clustering Algorithm

    Park, C. / Lee, H. / Musaffar, B. et al. | British Library Conference Proceedings | 2011