Algoritmos de heurísticas para o problema da t-admissibilidade

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorCunha, Luís Felipe Ignácio-
Autor(es): dc.contributorAraújo, Leandro Santiago de-
Autor(es): dc.contributorSantos, Thadeu Duarte-
Autor(es): dc.creatorMarciano, Eriky Nunes-
Data de aceite: dc.date.accessioned2025-08-21T20:16:12Z-
Data de disponibilização: dc.date.available2025-08-21T20:16:12Z-
Data de envio: dc.date.issued2025-02-21-
Data de envio: dc.date.issued2025-02-21-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/36818-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/1057929-
Descrição: dc.descriptionEste trabalho propõe duas novas heurísticas, voltadas para a geração de árvores t-spanners em grafos, além de comparar seu desempenho com métodos de força bruta e abordagens heurísticas estabelecidas na literatura. Os experimentos consistiram em avaliar as heurísticas em diversos tipos de grafos, incluindo Barabási-Albert, Erdos-Renyi, Watts-Strogatz e Bipartidos. Como resultado, observou-se que ambas as heurísticas podem igualar ou até superar as demais estratégias em cenários onde a complexidade do grafo torna inviáveis outras técnicas. Conclui-se que, apesar das limitações decorrentes da possibilidade de geração exponencial de árvores, as heurísticas demonstram um significativo potencial de otimização, apontando para direções futuras de pesquisa, como a utilização de estruturas de dados avançadas e paralelismo na construção de árvores, visando aprimorar sua robustez e aplicabilidade em grafos de grande porte.-
Descrição: dc.descriptionThis work proposes two new heuristics aimed at generating trees t-spanners in graphs, as well as comparing their performance against brute force methods and established heuristic approaches in the literature. The experiments involved evalu- ating these heuristics on various types of graphs, including Barab ́asi-Albert, Erd ̋os- R ́enyi, Watts-Strogatz, and Bipartite. The results indicate that both heuristics can match or even outperform other strategies in scenarios where graph complexity ren- ders alternative techniques impractical. It is concluded that, despite the limitations arising from the potential exponential generation of trees, the heuristics exhibit a significant optimization potential, pointing to future research directions such as the use of advanced data structures and parallelism in the tree construction process, aiming to improve their robustness and applicability in large-scale graphs.-
Descrição: dc.description35 f.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectHeurísticas-
Palavras-chave: dc.subjectGrafos-
Palavras-chave: dc.subjectArvores t-spanners-
Palavras-chave: dc.subjectHeurística-
Palavras-chave: dc.subjectGrafo-
Palavras-chave: dc.subjectAnálise comparativa-
Palavras-chave: dc.subjectHeuristics-
Palavras-chave: dc.subjectGraphs-
Palavras-chave: dc.subjectTree t-spanners-
Título: dc.titleAlgoritmos de heurísticas para o problema da t-admissibilidade-
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.