Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/96121
Title: Minimum Spanning Tree Algorithms, one-dimensional ranking and comparison.
Other Titles: Minimum Spanning Tree Algorithms, one-dimensional ranking and comparison.
Authors: Frieden, Marco Henrik
Orientador: Santos, José Luís Esteves dos
Keywords: árvores cobertura mínima; heap; estrutura dados; grafos; algoritmos; minimum spanning trees; algorithm; heaps; graphs; data structures
Issue Date: 17-Sep-2021
Serial title, monograph or event: Minimum Spanning Tree Algorithms, one-dimensional ranking and comparison.
Place of publication or event: Departamento de Matemática da Universidade de Coimbra
Abstract: Neste trabalho focamo-nos no problema de árvores de cobertura mínima (MST) e em implementações eficientes de o resolver, tal como no estudo da variante do problema clássico - ranking de MST's. Em particular, estudamos diferentes implementações de como obter estas árvores, usando estruturas de dados simples, como listas, e mais complexas, como \textit{heaps} binárias e \textit{heaps} de Fibonacci. Usando os largamente conhecidos algoritmos de Kruskal e Prim, comparamos todas as diferentes implementações, provando a grande eficiência destas estruras \textit{heap}, não apenas no sentido teórico mas comprovando com testes práticos, em particular para grafos completos. Também estudamos e desenvolvemos um algoritmo para a obtenção das $k$ melhores árvores de cobertura. Deixamos em aberto a continuação deste trabalho, com a sujestão de aplicar estas implementações em grafos multi-objetivo e usar o investigado para criar uma aplicação prática para o mundo corporativo ou industrial.--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
In this work we focus on the Minimum Spanning Tree (MST) problem and efficient implementations for it, as well as the study of a variant of the classical problem - ranking of MST's. In particular, we cover implementations of the attainment of such trees, with simple lists and more complex data structures such as binary and Fibonacci heaps. In combination with the most known Kruskal and Prim algorithms, we compare all the implementations to verify that the heaps do not only show themselves as theoretically more efficient, but also in practical cases, in particular for complete graphs. We also look and implement an algorithm for the attainment of the $k$ best spanning trees, using the implementations studied before. We leave open some possible continuation of this work, namely applying it to multi-objective graphs and turning the knowledge into a corporative or industrial application.------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Description: Dissertação de Mestrado em Matemática apresentada à Faculdade de Ciências e Tecnologia
URI: http://hdl.handle.net/10316/96121
Rights: openAccess
Appears in Collections:UC - Dissertações de Mestrado

Files in This Item:
File Description SizeFormat
Thesis.pdf768.39 kBAdobe PDFView/Open
Show full item record

Page view(s)

6
checked on Nov 25, 2021

Download(s)

10
checked on Nov 25, 2021

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons