Publicado em: 19/11/2012

Dissertação de Mestrado em Informática Teórica

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
INSTITUTO DE INFORMÁTICA
PROGRAMA DE POS-GRADUAÇÃO EM COMPUTAÇÃO
———————————————————
DEFESA DE DISSERTAÇÃO DE MESTRADO

Aluno: Bruno Menegola
Orientador: Prof. Dr. Marcus Rolf Peter Ritt

Título: A Study of the k-way Graph Partitioning Problem

Linha de Pesquisa: Informática Teórica – Fundamentos da Computação

Data: 22/11/2012
Hora: 15h30min
Local: Auditório Inferior. Prédio 43413(67) – Instituto de Informática

Banca Examinadora:
Prof. Dr. Marcelo de Oliveira Johann (UFRGS)
Profa. Dra. Maria Cláudia Silva Boeres (UFES)
Prof. Dr. Mario Inostroza Ponta (USACH)

Presidente da Banca: Prof. Dr. Marcus Rolf Peter Ritt

Resumo:

O 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 floor{epsilon n/k}, para algum epsilonin[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.

Palavras-Chave: Particionamento de Grafos, Heurísticas, Metaheurísticas,Algoritmos