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
ACESSO AO ARTIGO
http://libdigi.unicamp.br/document/?code=000105689Documentos 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