Heurísticas para o Problema de Particionamento de Grafos

Nome: Renato Stocco Bonatto
Tipo: Dissertação de mestrado acadêmico
Data de publicação: 26/08/2010
Orientador:

Nomeordem decrescente Papel
André Renato Sales Amaral Orientador

Banca:

Nomeordem decrescente Papel
André Renato Sales Amaral Orientador
Luis Ernesto Torres Guardiã Suplente Externo
Maria Claudia Silva Boeres Examinador Interno

Resumo: O problema de particionamento de grafos é um problema NP-DIFÍCIL e, portanto, torna-se viável investigá-lo utilizando métodos heurísticos e metaheurísticos. Famosas abordagens metaheurísticas podem ser encontradas aplicadas ao PPG, como Recozimento Simulado, Algoritmos Genéticos e Busca Tabu. Técnicas em multiníveis protagonizam o estado da arte em particionamento de grafos e consistem, basicamente, em comprimir o grafo original, particioná-lo e expandi-lo novamente ao grafo original.
Neste projeto de dissertação de mestrado, pretende-se desenvolver um algoritmo que utiliza a abordagem multinível, incorporando-o a uma interface gráfica, configurando um software multiplataforma de fácil utilização que particiona um grafo de forma eficiente, tanto em termos de qualidade de solução quanto em tempo de execução.

Acesso à informação
Transparência Pública

© 2013 Universidade Federal do Espírito Santo. Todos os direitos reservados.
Av. Fernando Ferrari, 514 - Goiabeiras, Vitória - ES | CEP 29075-910