Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/53008
Título: | A generic and highly efficient parallel variant of Borůvka's algorithm |
Autor(es): | Da Silva Sousa, Cristiano Mariano, Artur Proença, Alberto José |
Data: | 2015 |
Editora: | Institute of Electrical and Electronics Engineers Inc. |
Resumo(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. |
Tipo: | Artigo em ata de conferência |
URI: | https://hdl.handle.net/1822/53008 |
ISBN: | 9781479984909 |
DOI: | 10.1109/PDP.2015.72 |
Arbitragem científica: | yes |
Acesso: | Acesso aberto |
Aparece nas coleções: |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
boruvka_uminho_cameraready_v2.pdf | 292,27 kB | Adobe PDF | Ver/Abrir |