Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/456
Tipo: Dissertação
Título: Algoritmos BSP/CGM para o Fecho Transitivo
Autor(es): Vieira, Cristiano Costa Argemon
Abstract: Apresentamos duas estratégias e dois algoritmos BSP/CGM para computar o fecho transitivo de um digrafo. Nossas idéias foram obtidas através da avaliação dos resultados obtidos pelos algoritmos BSP/CGM de Alves et al. e Castro Jr.. Melhoramos o desempenho destes algoritmos diminuindo o tamanho das mensagens trocadas entre os processadores, a computação local e a quantidade de rodadas de comunicação entre os processadores. Os resultados obtidos através da implementação das nossas estratégias e algoritmos foram melhores que os resultados apresentados por outros autores.
We show two approaches and two BSP/CGM algorithms to compute a transitive closure of digraphs. Our ideas are based in a detailed observation of BSP/CGM algorithms presented by Alves et al. and Castro Jr.. We improved the algorithms performance by decreasing the message length changed between processors, the local computation and the number of communication rounds. The results obtained by implementations of our approaches and algorithms are better than the results obtained by other authors.
Palavras-chave: Programação Paralela
Algoritmos Gráficos
Algoritmos e Estruturas de Dados
Algoritmos Úteis e Específicos
Tipo de Acesso: Acesso Aberto
URI: https://repositorio.ufms.br/handle/123456789/456
Data do documento: 2006
Aparece nas coleções:Programa de Pós-graduação em Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Cristiano Costa Argemon Vieira.pdf401,55 kBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.