Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Protti, Fábio | - |
Autor(es): dc.contributor | Mafort, Rodrigo L. | - |
Autor(es): dc.contributor | Rosseti, Isabel Cristina Mello | - |
Autor(es): dc.contributor | Nepomuceno, Rogério Melo | - |
Autor(es): dc.creator | Vallim, Edoarda | - |
Data de aceite: dc.date.accessioned | 2024-07-11T18:36:40Z | - |
Data de disponibilização: dc.date.available | 2024-07-11T18:36:40Z | - |
Data de envio: dc.date.issued | 2022-07-18 | - |
Data de envio: dc.date.issued | 2022-07-18 | - |
Data de envio: dc.date.issued | 2020 | - |
Fonte completa do material: dc.identifier | http://app.uff.br/riuff/handle/1/25731 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/773891 | - |
Descrição: dc.description | Este 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.description | This 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.description | 48 p. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Direitos: dc.rights | Open Access | - |
Direitos: dc.rights | CC-BY-SA | - |
Palavras-chave: dc.subject | Árvore Geradora | - |
Palavras-chave: dc.subject | Algoritmos em Grafos | - |
Palavras-chave: dc.subject | MetaheurÍsticas | - |
Palavras-chave: dc.subject | Grafos Completos | - |
Palavras-chave: dc.subject | Metaheurística híbrida | - |
Palavras-chave: dc.subject | Algoritmo em grafos | - |
Palavras-chave: dc.subject | Grafo | - |
Palavras-chave: dc.subject | Spanning Tree | - |
Palavras-chave: dc.subject | Graph Algorithms | - |
Palavras-chave: dc.subject | Metaheuristics | - |
Palavras-chave: dc.subject | Complete Graphs | - |
Título: dc.title | Estudo de vizinhanças para a solução do problema da árvore geradora mínima com diâmetro limitado | - |
Tipo de arquivo: dc.type | Trabalho de conclusão de curso | - |
Aparece nas coleções: | Repositório Institucional da Universidade Federal Fluminense - RiUFF |
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: