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

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorCarvalho, Marco Antonio Moreira de-
Autor(es): dc.contributorCarvalho, Marco Antonio Moreira de-
Autor(es): dc.contributorSouza, Marcone Jamilson Freitas-
Autor(es): dc.contributorSantos, André Gustavo dos-
Autor(es): dc.contributorLima, Joubert de Castro-
Autor(es): dc.creatorSantos, Vinícius Gandra Martins-
Data de aceite: dc.date.accessioned2025-08-21T15:16:56Z-
Data de disponibilização: dc.date.available2025-08-21T15:16:56Z-
Data de envio: dc.date.issued2018-11-29-
Data de envio: dc.date.issued2018-11-29-
Data de envio: dc.date.issued2018-
Fonte completa do material: dc.identifierhttp://www.repositorio.ufop.br/handle/123456789/10571-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/1009080-
Descrição: 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.-
Descrição: dc.descriptionO 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.-
Descrição: dc.descriptionThe 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.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsaberto-
Direitos: dc.rightsAutorizaçã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.-
Palavras-chave: dc.subjectHeurística-
Palavras-chave: dc.subjectTeoria dos grafos-
Palavras-chave: dc.subjectOtimização combinatória-
Título: dc.titleBusca adaptativa em grandes vizinhanças aplicada à minimização da largura de corte em grafos.-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional - UFOP

Não existem arquivos associados a este item.