Estratégia de partição em caminhos para o problema da árvore geradora com número mínimo de ramificações

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorProtti, Fábio-
Autor(es): dc.contributorMafort, Rodrigo L.-
Autor(es): dc.contributorBravo, Raquel-
Autor(es): dc.contributorMartins, Simone-
Autor(es): dc.creatorSantos, Victória Granja Amorim dos-
Data de aceite: dc.date.accessioned2024-07-11T18:13:21Z-
Data de disponibilização: dc.date.available2024-07-11T18:13:21Z-
Data de envio: dc.date.issued2024-02-29-
Data de envio: dc.date.issued2024-02-29-
Fonte completa do material: dc.identifierhttp://app.uff.br/riuff/handle/1/32507-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/766095-
Descrição: dc.descriptionO problema de encontrar uma árvore geradora com o menor número de ramificações em um grafo não direcionado é conhecido na literatura como “Minimum Branch Vertices Problem” ou “MBV”. Foi demonstrado que o MBV é um problema da classe NP-Difícil, e por isso existem diferentes abordagens que tentam lidar com sua complexidade computacional. As heurísticas são boas ferramentas para otimização, e a partir delas é possível obter um resultado de qualidade com tempo viável. Neste trabalho, desenvolvemos uma heurística baseada nos algoritmos de Prim e Kruskal-
Descrição: dc.descriptionThe problem of finding a spanning tree with the minimum number of branches is known in the literature as the “Minimum Branch Vertices Problem” or “MBV”. It has been shown that MBV is an NP-hard problem, and for this reason there are different approaches that try to deal with its computational complexity. Heuristics serve as practical tools for optimization, leading to good results within reasonable running times. This work proposes the development of two heuristics based on Prim and Kruskal algorithms-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectGrafo-
Palavras-chave: dc.subjectArvore geradora-
Palavras-chave: dc.subjectRamificações-
Palavras-chave: dc.subjectMBV-
Palavras-chave: dc.subjectGrafo-
Palavras-chave: dc.subjectHeurística-
Palavras-chave: dc.subjectAlgoritmo computacional-
Palavras-chave: dc.subjectGraph-
Palavras-chave: dc.subjectBranches-
Palavras-chave: dc.subjectSpanning tree-
Título: dc.titleEstratégia de partição em caminhos para o problema da árvore geradora com número mínimo de ramificações-
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.