Busca adaptativa em grandes vizinhanças aplicada à minimização da largura de corte em grafos.

Simple item page
dc.contributor.advisorCarvalho, Marco Antonio Moreira dept_BR
dc.contributor.authorSantos, Vinícius Gandra Martins
dc.contributor.refereeCarvalho, Marco Antonio Moreira dept_BR
dc.contributor.refereeSouza, Marcone Jamilson Freitaspt_BR
dc.contributor.refereeSantos, André Gustavo dospt_BR
dc.contributor.refereeLima, Joubert de Castropt_BR
dc.date.accessioned2018-11-29T12:05:06Z
dc.date.available2018-11-29T12:05:06Z
dc.date.issued2018
dc.descriptionPrograma 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.pt_BR
dc.description.abstractO 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.pt_BR
dc.description.abstractenThe cutwidth minimization problem (CMP) consists in determining a linear layout of the vertices of a graph that minimizes the maximum cardinality of edges cut between any consecutive pair of vertices. This problem has applications, for instance, in design of very large-scale integration circuits, graph drawing, and compiler design, among others. The CMP is an NP-Hard problem and presents a challenge to exact methods and heuristics. In this study, the metaheuristic adaptive large neighborhood search is applied for the first time to the CMP. The computational experiments include 11,786 benchmark instances from the literature, and the obtained results are compared with those of the state-of-the-art methods. The proposed method was demonstrated to be competitive, as it matched most of proved optimal and best known results, improved some of the (not proved optimal) best known solutions, and provided the first upper bounds for unsolved instances.pt_BR
dc.identifier.citationSANTOS, 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.pt_BR
dc.identifier.urihttp://www.repositorio.ufop.br/handle/123456789/10571
dc.language.isopt_BRpt_BR
dc.rightsabertopt_BR
dc.rights.licenseAutorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 29/11/2018 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais nem a adaptação.pt_BR
dc.subjectHeurísticapt_BR
dc.subjectTeoria dos grafospt_BR
dc.subjectOtimização combinatóriapt_BR
dc.titleBusca adaptativa em grandes vizinhanças aplicada à minimização da largura de corte em grafos.pt_BR
dc.typeDissertacaopt_BR
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
DISSERTAÇÃO_BuscaAdaptativaGrandes.pdf
Size:
1.51 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
924 B
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
PPGCC - Mestrado (Dissertações)