Title :
Parallel implementation of minimum spanning tree algorithms using MPI
Author :
Loncar, V. ; Skrbic, S.
Author_Institution :
Dept. for Math. an Inf., Univ. of Novi Sad, Novi Sad, Serbia
Abstract :
In this paper we study parallel algorithms for finding minimum spanning tree of a graph. We present two algorithms, based on sequential algorithms of Prim and Kruskal, targeting message passing parallel machine with distributed memory. First algorithm runs in O(n2=p+n log p) and second algorithm runs in O(n2=p + n2 log p).
Keywords :
computational complexity; distributed memory systems; message passing; parallel algorithms; parallel machines; trees (mathematics); MPI; computational complexity; distributed memory; graph; message passing parallel machine; minimum spanning tree algorithms; parallel algorithms; parallel implementation; sequential algorithms; Minimum spanning tree; distributed memory computer; message passing; parallel algorithms;
Conference_Titel :
Computational Intelligence and Informatics (CINTI), 2012 IEEE 13th International Symposium on
Conference_Location :
Budapest
Print_ISBN :
978-1-4673-5205-5
Electronic_ISBN :
978-1-4673-5210-9
DOI :
10.1109/CINTI.2012.6496797
