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

AUTOR(ES)

Carlos Fernando Bella Cruz

DATA DE PUBLICAÇÃO

1996

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

ASSUNTO(S)

otimização combinatoria algoritmos paralelos teoria dos grafos

Documentos Relacionados

• Uma implementação paralela híbrida para o problema do caixeiro viajante usando algoritmos genéticos, GRASP e aprendizagem por reforço
• MPI: uma ferramenta para implementação paralela
• Algoritmos para emparelhamentos em grafos bipartidos
• Algorithms for classification and partitioning in graphs
• Implementação e análise de algoritmos para coloração de arestas