Algoritmos para emparelhamento em grafos e uma implementação paralela

Autor(es)

Carlos Fernando Bella Cruz

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Ciência da Computação
• Data de defesa: 1996-04-17

Membros da banca

João Carlos Setubal; Ricardo Dahab; Routo Terada

• Orientador: João Carlos Setubal

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. (AU)

• Processo FAPESP: 94/04158-5 - Algoritmos para emparelhamento em grafos e uma implementacao paralela.
• Beneficiário: Carlos Fernando Bella Cruz
• Modalidade de apoio: Bolsas no Brasil - Mestrado