Estudo de vizinhanças para a solução do problema da árvore geradora mínima com diâmetro limitado

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorProtti, Fábio-
Autor(es): dc.contributorMafort, Rodrigo L.-
Autor(es): dc.contributorRosseti, Isabel Cristina Mello-
Autor(es): dc.contributorNepomuceno, Rogério Melo-
Autor(es): dc.creatorVallim, Edoarda-
Data de aceite: dc.date.accessioned2024-07-11T18:36:40Z-
Data de disponibilização: dc.date.available2024-07-11T18:36:40Z-
Data de envio: dc.date.issued2022-07-18-
Data de envio: dc.date.issued2022-07-18-
Data de envio: dc.date.issued2020-
Fonte completa do material: dc.identifierhttp://app.uff.br/riuff/handle/1/25731-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/773891-
Descrição: dc.descriptionEste trabalho aborda o Problema da Arvore Geradora Mínima com Diâmetro Limitado (em inglˆes, Bounded-Diameter Minimum Spanning Tree Problem - BDMSTP), definido como segue: Dado um grafo G onde cada aresta xy tem um custo positivo wxy, o objetivo é encontrar uma árvore geradora ótima de G cujo diâmetro não exceda um dado número inteiro positivo D ≥ 2. As aplicações do BDMSTP contemplam redes de telecomunicações e projetos de fibra ótica, problemas de compressão de dados e projeto de sistemas distribuídos. Com base na abordagem feita em [31], que utiliza Iterated Local Search (ILS) com cinco novas vizinhan ̧cas para a Busca Local (baseada no método RVND - Randomized Variable Neighborhood Descent) e quatro novos movimentos de perturbação, conduzimos um estudo comparativo das vizinhanças e realizamos testes computacionais em instâncias da OR-Library com 250, 500 e 1000 nós. Os experimentos mostraram que o uso dessas vizinhanças alcança excelentes resultados em termos de qualidade das soluções obtidas.-
Descrição: dc.descriptionThis work deals with the Bounded-Diameter Minimum Spanning Tree Problem (BDMSTP), defined as follows: Given a graph G where each edge xy has a positive cost wxy, the goal is to find an optimal spanning tree of G whose diameter does not exceed a prescribed positive integer D ≥ 2. Applications of the BDMSTP appear in telecommunication network and fiber optic projects, data compression problems, and distributed systems design. Based on the Iterated Local Search approach described in [31], which uses five new neighborhoods for the local search (consisting of the Variable Neighborhood Descent method) and four new perturbation moves, we conduct a comparative study of the neighborhoods and perform computational tests on OR-Library graph instances with 250, 500, and 1000 nodes. The experiments show that the use of the neighborhoods leads to good computational results in terms of solution quality.-
Descrição: dc.description48 p.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectÁrvore Geradora-
Palavras-chave: dc.subjectAlgoritmos em Grafos-
Palavras-chave: dc.subjectMetaheurÍsticas-
Palavras-chave: dc.subjectGrafos Completos-
Palavras-chave: dc.subjectMetaheurística híbrida-
Palavras-chave: dc.subjectAlgoritmo em grafos-
Palavras-chave: dc.subjectGrafo-
Palavras-chave: dc.subjectSpanning Tree-
Palavras-chave: dc.subjectGraph Algorithms-
Palavras-chave: dc.subjectMetaheuristics-
Palavras-chave: dc.subjectComplete Graphs-
Título: dc.titleEstudo de vizinhanças para a solução do problema da árvore geradora mínima com diâmetro limitado-
Tipo de arquivo: dc.typeTrabalho de conclusão de curso-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.