Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/96121
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Santos, José Luís Esteves dos | - |
dc.contributor.author | Frieden, Marco Henrik | - |
dc.date.accessioned | 2021-10-25T22:05:10Z | - |
dc.date.available | 2021-10-25T22:05:10Z | - |
dc.date.issued | 2021-09-17 | - |
dc.date.submitted | 2021-10-25 | - |
dc.identifier.uri | https://hdl.handle.net/10316/96121 | - |
dc.description | Dissertação de Mestrado em Matemática apresentada à Faculdade de Ciências e Tecnologia | - |
dc.description.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.-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | por |
dc.description.abstract | 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.------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | eng |
dc.language.iso | eng | - |
dc.rights | openAccess | - |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | - |
dc.subject | árvores cobertura mínima | por |
dc.subject | heap | por |
dc.subject | estrutura dados | por |
dc.subject | grafos | por |
dc.subject | algoritmos | por |
dc.subject | minimum spanning trees | eng |
dc.subject | algorithm | eng |
dc.subject | heaps | eng |
dc.subject | graphs | eng |
dc.subject | data structures | eng |
dc.title | Minimum Spanning Tree Algorithms, one-dimensional ranking and comparison. | eng |
dc.title.alternative | Minimum Spanning Tree Algorithms, one-dimensional ranking and comparison. | por |
dc.type | masterThesis | - |
degois.publication.location | Departamento de Matemática da Universidade de Coimbra | - |
degois.publication.title | Minimum Spanning Tree Algorithms, one-dimensional ranking and comparison. | eng |
dc.peerreviewed | yes | - |
dc.identifier.tid | 202778797 | - |
thesis.degree.discipline | Matemática | - |
thesis.degree.grantor | Universidade de Coimbra | - |
thesis.degree.level | 1 | - |
thesis.degree.name | Mestrado em Matemática | - |
uc.degree.grantorUnit | Faculdade de Ciências e Tecnologia - Departamento de Matemática | - |
uc.degree.grantorID | 0500 | - |
uc.contributor.author | Frieden, Marco Henrik::0000-0001-5746-1017 | - |
uc.degree.classification | 12 | - |
uc.degree.presidentejuri | Gouveia, João Eduardo da Silveira | - |
uc.degree.elementojuri | Soares, João Luís Cardoso | - |
uc.degree.elementojuri | Santos, José Luís Esteves dos | - |
uc.contributor.advisor | Santos, José Luís Esteves dos::0000-0002-2727-6774 | - |
item.openairetype | masterThesis | - |
item.languageiso639-1 | en | - |
item.openairecristype | http://purl.org/coar/resource_type/c_18cf | - |
item.cerifentitytype | Publications | - |
item.grantfulltext | open | - |
item.fulltext | Com Texto completo | - |
Appears in Collections: | UC - Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Thesis.pdf | 768.39 kB | Adobe PDF | View/Open |
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