Show simple item record

dc.contributor.advisorRitt, Marcus Rolf Peterpt_BR
dc.contributor.authorMenegola, Brunopt_BR
dc.date.accessioned2013-03-02T01:40:38Zpt_BR
dc.date.issued2012pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/67181pt_BR
dc.description.abstractO problema de particionamento balanceado de grafos consiste em encontrar uma partição de tamanho k dos vértices de um grafo, minimizando o número de arestas que participam do corte tal que o tamanho de nenhuma parte exceda [en~k], para algum e e > [1, k). Essa dissertação estuda esse problema, apresentando uma revisão recente de heurísticas construtivas, heurísticas de refinamento e técnicas multinível. Também propomos um novo algoritmo híbrido para resolver esse problema de particionamento. Nós mostramos como diversas estratégias para construir e aprimorar partições, assim como algumas novas propostas, podem ser integradas para formar um GRASP com path-relinking. Reportamos experimentos computacionais que mostram que essa abordagem obtém soluções competitivas com particionadores no estado-da-arte. Em particular, o algoritmo híbrido é capaz de encontrar novos melhores valores conhecidos em algumas das menores instâncias, indicando que tem uma contribuição qualitativa comparado aos métodos existentes.pt_BR
dc.description.abstractThe balanced graph partitioning problem asks to find a k-partition of the vertex set of an undirected graph, which minimizes the total cut size and such that the size of no part exceeds en/k , for some ee > [1, k]. This dissertation studies this problem, providing a recent review of constructive heuristics, refinement heuristics and multilevel techniques. We also propose a new hybrid algorithm for solving this partitioning problem. We show how several good existing strategies for constructing and improving partitions, as well as some newly proposed ones, can be integrated to form a GRASP with path-relinking. We report computational experiments that show that this approach obtains solutions competitive with state-of-the-art partitioners. In particular, the hybrid algorithm is able to find new best known values in some of the smaller instances, indicating that it can make a qualitative contribution compared to existing methods.en
dc.format.mimetypeapplication/pdf
dc.language.isoengpt_BR
dc.rightsOpen Accessen
dc.subjectGraph partitioningen
dc.subjectGrafospt_BR
dc.subjectHeuristicsen
dc.subjectTeoria : Grafospt_BR
dc.subjectMetaheuristicsen
dc.subjectAlgorithmsen
dc.titleA study of the k-way graph partitioning problempt_BR
dc.title.alternativeUm estudo do problema de particionamento de grafos em k-partes pt_BR
dc.typeDissertaçãopt_BR
dc.identifier.nrb000872783pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Informáticapt_BR
dc.degree.programPrograma de Pós-Graduação em Computaçãopt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2012pt_BR
dc.degree.levelmestradopt_BR


Files in this item

Thumbnail
   

This item is licensed under a Creative Commons License

Show simple item record