Parallelization of Minimum Spanning Tree Algorithms Using Distributed Memory Architectures  

Oleh:

Loncar, Vladimir ; Skrbic, Srdjan ; Balaz, Antun

Jenis: Article from Books - E-Book
Dalam koleksi: Transactions on Engineering Technologies: Special Volume of the World Congress on Engineering 2013, page 543-554.
Topik: Distributed memory; Kruskal; MPI; MST; Paralellization; Prim
Fulltext: 39_978-94-017-8831-1_Loncar_Skrbic_Balaz.pdf (402.16KB)

Isi artikel

Finding a minimum spanning tree of a graph is a well known problem in graph theory with many practical applications. We study serial variants of Prim’s and Kruskal’s algorithm and present their parallelization targeting message passing parallel machine with distributed memory. We consider large graphs that can not fit into memory of one process. Experimental results show that Prim’s algorithm is a good choice for dense graphs while Kruskal’s algorithm is better for sparse ones. Poor scalability of Prim’s algorithm comes from its high communication cost while Kruskal’s algorithm showed much better scaling to larger number of processes.

Opini Anda

Klik untuk menuliskan opini Anda tentang koleksi ini!

Kembali