Busca adaptativa em grandes vizinhanças aplicada à minimização da largura de corte em grafos.
No Thumbnail Available
Date
2018
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
O problema de Minimização da 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.
Description
Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.
Keywords
Heurística, Teoria dos grafos, Otimização combinatória
Citation
SANTOS, Vinícius Gandra Martins. Busca adaptativa em grandes vizinhanças aplicada à minimização da largura de corte em grafos. 2018. 75 f. Dissertação (Mestrado em Ciência da Computação) - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2018.