Algoritmo BSP/CGM para o Problema do Fluxo Máximo em redes
AUTOR(ES)
Roberto Aragy Xavier Junior
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
17/12/2010
RESUMO
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.
ASSUNTO(S)
fluxo máximo computação paralela modelo bsp/cgm ciencia da computacao max-flow parallel computing bsp/cgm model
