Return to search

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

Orientador: João Carlos Setubal / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da ComputaçãO / Made available in DSpace on 2018-07-21T05:57:00Z (GMT). No. of bitstreams: 1
Cruz_CarlosFernandoBella_M.pdf: 2090300 bytes, checksum: c7ddb8099b731928143e26f66c270afc (MD5)
Previous issue date: 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. / 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. / Mestrado / Mestre em Ciência da Computação

Identiferoai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/276023
Date17 April 1996
CreatorsCruz, Carlos Fernando Bella
ContributorsUNIVERSIDADE ESTADUAL DE CAMPINAS, Setubal, João Carlos, 1957-, Dahab, Ricardo, Terada, Routo
Publisher[s.n.], Universidade Estadual de Campinas. Instituto de Matemática, Estatística e Computação Científica, Programa de Pós-Graduação em Matemática
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Format84f., application/octet-stream
Sourcereponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0018 seconds