Please use this identifier to cite or link to this item: http://hdl.handle.net/1822/53008

TitleA generic and highly efficient parallel variant of Borůvka's algorithm
Author(s)Da Silva Sousa, Cristiano
Mariano, Artur
Proença, Alberto José
Issue date2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Abstract(s)This paper presents (i) a parallel, platformindependent variant of Borůvka's algorithm, an efficient Minimum Spanning Tree (MST) solver, and (ii) a comprehensive comparison of MST-solver implementations, both on multi-core CPU-chips and GPUs. The core of our variant is an effective and explicit contraction of the graph. Our multi-core CPU implementation scales linearly up to 8 threads, whereas the GPU implementation performs considerably better than the optimal number of threads running on the CPU. We also show that our implementations outperform all other parallel MST-solver implementations in (ii), for a broad set of publicly available roadnetwork graphs.
TypeconferencePaper
URIhttp://hdl.handle.net/1822/53008
ISBN9781479984909
DOI10.1109/PDP.2015.72
Peer-Reviewedyes
AccessopenAccess
Appears in Collections:CAlg - Artigos em livros de atas/Papers in proceedings

Files in This Item:
File Description SizeFormat 
boruvka_uminho_cameraready_v2.pdf292,27 kBAdobe PDFView/Open

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu Currículo DeGóis