Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/8540
Title: | Distributed memory parallel algorithms for minimum spanning trees | Authors: | Lončar V. Škrbić, S. Balaž, A. |
Issue Date: | 25-Nov-2013 | Journal: | Lecture Notes in Engineering and Computer Science | Abstract: | 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. | URI: | https://open.uns.ac.rs/handle/123456789/8540 | ISBN: | 9789881925282 | ISSN: | 20780958 |
Appears in Collections: | PMF Publikacije/Publications |
Show full item record
SCOPUSTM
Citations
1
checked on Feb 22, 2020
Page view(s)
25
Last Week
10
10
Last month
0
0
checked on May 10, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.