Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

New BSP/CGM algorithms for spanning trees

Texto completo
Autor(es):
de Alencar Vasconcellos, Jucele Franca [1] ; Caceres, Edson Norberto [1] ; Mongelli, Henrique [1] ; Song, Siang Wun [2] ; Dehne, Frank [3] ; Szwarcfiter, Jayme Luiz [4]
Número total de Autores: 6
Afiliação do(s) autor(es):
[1] Univ Fed Mato Grosso do Sul, Coll Comp, Campo Grande - Brazil
[2] Univ Sao Paulo, Inst Math & Stat, Sao Paulo - Brazil
[3] Carleton Univ, Sch Comp Sci, Ottawa, ON - Canada
[4] Univ Fed Rio de Janeiro, COPPE, NCE, Rio De Janeiro - Brazil
Número total de Afiliações: 4
Tipo de documento: Artigo Científico
Fonte: INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS; v. 33, n. 3, SI, p. 444-461, MAY 2019.
Citações Web of Science: 0
Resumo

Computing a spanning tree (ST) and a minimum ST (MST) of a graph are fundamental problems in graph theory and arise as a subproblem in many applications. In this article, we propose parallel algorithms to these problems. One of the steps of previous parallel MST algorithms relies on the heavy use of parallel list ranking which, though efficient in theory, is very time-consuming in practice. Using a different approach with a graph decomposition, we devised new parallel algorithms that do not make use of the list ranking procedure. We proved that our algorithms are correct, and for a graph G=(V,E), |V|=n, and |E|=m, the algorithms can be executed on a Bulk Synchronous Parallel/Coarse Grained Multicomputer (BSP/CGM) model using O(log p) communications rounds with O(n+mp) computation time for each round. To show that our algorithms have good performance on real parallel machines, we have implemented them on graphics processing unit. The obtained speedups are competitive and showed that the BSP/CGM model is suitable for designing general purpose parallel algorithms. (AU)

Processo FAPESP: 14/50937-1 - INCT 2014: da Internet do Futuro
Beneficiário:Fabio Kon
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 15/24485-9 - Internet do futuro aplicada a cidades inteligentes
Beneficiário:Fabio Kon
Linha de fomento: Auxílio à Pesquisa - Temático