Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Carvalho, Marco Antonio Moreira de | - |
Autor(es): dc.contributor | Carvalho, Marco Antonio Moreira de | - |
Autor(es): dc.contributor | Souza, Marcone Jamilson Freitas | - |
Autor(es): dc.contributor | Santos, André Gustavo dos | - |
Autor(es): dc.contributor | Lima, Joubert de Castro | - |
Autor(es): dc.creator | Santos, Vinícius Gandra Martins | - |
Data de aceite: dc.date.accessioned | 2025-08-21T15:16:56Z | - |
Data de disponibilização: dc.date.available | 2025-08-21T15:16:56Z | - |
Data de envio: dc.date.issued | 2018-11-29 | - |
Data de envio: dc.date.issued | 2018-11-29 | - |
Data de envio: dc.date.issued | 2018 | - |
Fonte completa do material: dc.identifier | http://www.repositorio.ufop.br/handle/123456789/10571 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/1009080 | - |
Descrição: dc.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. | - |
Descrição: dc.description | 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. | - |
Descrição: dc.description | The 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.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Direitos: dc.rights | aberto | - |
Direitos: dc.rights | Autorizaçã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.subject | Heurística | - |
Palavras-chave: dc.subject | Teoria dos grafos | - |
Palavras-chave: dc.subject | Otimização combinatória | - |
Título: dc.title | Busca adaptativa em grandes vizinhanças aplicada à minimização da largura de corte em grafos. | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositório Institucional - UFOP |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: