Orientador: João Carlos Setubal

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação

Resumo: Abordamos os principais algoritmos para o problema de emparelhamento máximo em grafos genéricos e desenvolvemos uma implementação paralela eficiente na prática, baseada no algoritmo seqüencial de Edmonds. Por prática entendemos uma implementação eficiente num multiprocessador de memória com...

Resumo: Abordamos os principais algoritmos para o problema de emparelhamento máximo em grafos genéricos e desenvolvemos uma implementação paralela eficiente na prática, baseada no algoritmo seqüencial de Edmonds. Por prática entendemos uma implementação eficiente num multiprocessador de memória com partilhada. A implementação consiste em permitir que cada processador procure caminhos aumentantes no grafo de forma assíncrona e independente dos demais. Embora a busca ocorra de forma paralela, o aumento do emparelhamento é feito por somente 1 processador por vez, o que garante a corretude do algoritmo sem incorrrer em atraso significativo no tempo de execução. O desenvolvimento da implementação teve como antecedente uma experiência negativa de paralelização baseada no algoritmo de Micali e Vazirani.

Abstract: In this work we present the most important matching algorithms for general graphs and develop an efficient parallel implementation in practice based on Edmonds'matching algorithm. By practice we mean an efficient implementation on a shared memory multiprocessor. The implementation allows...

Abstract: In this work we present the most important matching algorithms for general graphs and develop an efficient parallel implementation in practice based on Edmonds'matching algorithm. By practice we mean an efficient implementation on a shared memory multiprocessor. The implementation allows each processor to find augmenting paths assinchronously and independently of each other. Each matching augmentation is done by only one processor, and this makes the algorithm correct without causing significant delay in the execution time, in practice. The development of this implementation was made after a nega tive experience of paralelization based on the sequential algorithm of Micali and Vazirani.