Qualificação de mestrado do discente Vinícius Gandra, dia 11/05/18.

Qualificação de mestrado do discente Vinícius Gandra, dia 11/05/18, as 15:30 na Sala de Seminários do DECOM - ICEB III.

Título:
Busca Adaptativa em Grandes Vizinhanças Aplicada à Minimização da Largura de Corte em Grafos

Resumo:
O problema de Largura de Corte em Grafos (ou CMP, do inglês Cutwidth Minimization Problem) consiste em determinar um leiaute linear para um grafo de forma a minimizar a quantidade máxima de arestas que cruzam cada par de vértices consecutivos. Esse problema pode ser encontrado no projeto de circuitos integrados de larga escala, desenho de diagramas de grafos e projeto de compiladores, entre outros. O CMP é um problema NP-Difícil e se apresenta como um desafio para métodos exatos e heurísticas. Neste trabalho, é reportada pela primeira vez na literatura a aplicação do método metaheurístico Busca Adaptativa em Grandes Vizinhanças (Adaptive Large Neighborhood Search) para solução do CMP. Os experimentos computacionais envolvem 252 instâncias da literatura e os resultados encontrados são comparados com o atual estado da arte. O método proposto se mostra competitivo, sendo capaz de igualar a maior parte dos resultados da literatura.