Defesa de Dissertação Vinícius Gandra M. Santos, dia 23/11/2018, as 16:00, sala de seminários DECOM.

Defesa de Dissertação Vinícius Gandra M. Santos, dia 23/11/2018, as 16:00, sala de seminários DECOM - ICEB III

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

Banca: prof. Dr. Marco Antônio de Carvalho - UFOP; Prof. Dr. Marcone Jamilson de Souza - UFOP; Prof. Dr. André Gustavo dos Santos - UFV.

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, no desenho de diagramas de grafos e no 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 11.786 instâncias de quatro conjuntos 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 maioria dos resultados comprovadamente ótimos e melhores resultados conhecidos, além de melhorar alguns resultados que não foram provados ótimos e encontrar pela primeira vez limitantes superiores para instâncias não resolvidas.

Departamento de Computação  |  ICEB  |  Universidade Federal de Ouro Preto
Campus Universitário Morro do Cruzeiro  |  CEP 35400-000  |  Ouro Preto - MG, Brasil
Telefone: +55 31 3559-1692  |  decom@ufop.edu.br