Please use this identifier to cite or link to this item: https://hdl.handle.net/10316/96121
DC FieldValueLanguage
dc.contributor.advisorSantos, José Luís Esteves dos-
dc.contributor.authorFrieden, Marco Henrik-
dc.date.accessioned2021-10-25T22:05:10Z-
dc.date.available2021-10-25T22:05:10Z-
dc.date.issued2021-09-17-
dc.date.submitted2021-10-25-
dc.identifier.urihttps://hdl.handle.net/10316/96121-
dc.descriptionDissertação de Mestrado em Matemática apresentada à Faculdade de Ciências e Tecnologia-
dc.description.abstractNeste 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.--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------por
dc.description.abstractIn 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.------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------eng
dc.language.isoeng-
dc.rightsopenAccess-
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/-
dc.subjectárvores cobertura mínimapor
dc.subjectheappor
dc.subjectestrutura dadospor
dc.subjectgrafospor
dc.subjectalgoritmospor
dc.subjectminimum spanning treeseng
dc.subjectalgorithmeng
dc.subjectheapseng
dc.subjectgraphseng
dc.subjectdata structureseng
dc.titleMinimum Spanning Tree Algorithms, one-dimensional ranking and comparison.eng
dc.title.alternativeMinimum Spanning Tree Algorithms, one-dimensional ranking and comparison.por
dc.typemasterThesis-
degois.publication.locationDepartamento de Matemática da Universidade de Coimbra-
degois.publication.titleMinimum Spanning Tree Algorithms, one-dimensional ranking and comparison.eng
dc.peerreviewedyes-
dc.identifier.tid202778797-
thesis.degree.disciplineMatemática-
thesis.degree.grantorUniversidade de Coimbra-
thesis.degree.level1-
thesis.degree.nameMestrado em Matemática-
uc.degree.grantorUnitFaculdade de Ciências e Tecnologia - Departamento de Matemática-
uc.degree.grantorID0500-
uc.contributor.authorFrieden, Marco Henrik::0000-0001-5746-1017-
uc.degree.classification12-
uc.degree.presidentejuriGouveia, João Eduardo da Silveira-
uc.degree.elementojuriSoares, João Luís Cardoso-
uc.degree.elementojuriSantos, José Luís Esteves dos-
uc.contributor.advisorSantos, José Luís Esteves dos::0000-0002-2727-6774-
item.openairetypemasterThesis-
item.languageiso639-1en-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.cerifentitytypePublications-
item.grantfulltextopen-
item.fulltextCom Texto completo-
Appears in Collections:UC - Dissertações de Mestrado
Files in This Item:
File Description SizeFormat
Thesis.pdf768.39 kBAdobe PDFView/Open
Show simple item record

Page view(s)

83
checked on Mar 26, 2024

Download(s)

146
checked on Mar 26, 2024

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons