Algoritmos para emparelhamento em grafos e uma implementação paralela
Carlos Fernando Bella Cruz
DISSERTAÇÃO
Português
T/UNICAMP C889a
Campinas, SP : [s.n.], 1996.
84f.
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...
Ver mais
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.
Ver menos
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...
Ver mais
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.
Ver menos
Algoritmos para emparelhamento em grafos e uma implementação paralela
Carlos Fernando Bella Cruz
Algoritmos para emparelhamento em grafos e uma implementação paralela
Carlos Fernando Bella Cruz
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra