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 ao documento

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