Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/508
Tipo: Dissertação
Título: Algoritmo BSP/CGM para o Problema do Fluxo Máximo em redes
Autor(es): Xavier Junior, Roberto Aragy
Abstract: Neste trabalho estudamos o Problema do Fluxo Máximo sob a ótica do paradigma do paralelismo. O objetivo geral desta dissertação é discutir os métodos sequenciais e paralelos para o Problema do Fluxo Máximo em Redes. Uma das contribuições deste trabalho é produzir um texto em português que trate dos principais algoritmos para o problema. Outra contribuição relevante é que propomos um novo algoritmo paralelo BSP/CGM que gasta O(p) rodadas de comunicação para duas classes especiais de grafos. Nos resultados dos testes realizados em uma máquina paralela tipo Beowulf de 12 nós, observamos speed-ups superlineares de 1,85 até 107 com uso de classes de grafos especiais.
Palavras-chave: Programação Paralela
Teoria dos Grafos
Algoritmos Úteis e Específicos
Programação Inteira e Fluxos em Rede
Tipo de Acesso: Acesso Aberto
URI: https://repositorio.ufms.br/handle/123456789/508
Data do documento: 2010
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 
Roberto Aragy Xavier Junior.pdf836,89 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.