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:
Nome |
Papel |
|---|---|
| ANDRÉ RENATO SALES AMARAL | Orientador |
Banca:
| Nome |
Papel |
|---|---|
| MARIA CLAUDIA SILVA BOERES | Examinador Interno |
| LUIS ERNESTO TORRES GUARDIÃ | Suplente Externo |
| ANDRÉ RENATO SALES AMARAL | Orientador |
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.
