FenixEdu™

Dissertação

Computing Geodesic Tree Distances with the GTP Algorithm EVALUATED

Detalhes: A geometria do espaço de árvores $\mathcal{T}_n$ introduzida por Billera, Holmes e Vogtmann possibilita a comparação de árvores filogenéticas através da distância geodésica, i.e. o comprimento do caminho mais curto entre duas árvores. Nesta tese estudamos e implementamos o primeiro algoritmo de tempo polinomial para encontrar geodésicas em $\mathcal{T}_n$, que foi proposto por Owen e Provan. Estudamos outros problemas e algoritmos relacionados com o problema de encontrar geodésicas em $\mathcal{T}_n$ (o \textit{Geodesic Treepath Problem}), nomeadamente no problema do fluxo máximo numa rede. Os nossos resultados demonstram que a distância geodésica pode ser eficientemente calculada em tempo útil com as escolhas corretas de algoritmos e estruturas de dados, confirmando a nossa análise teórica.
Keywords: Distância geodésica, Árvore filogenética, Geodesic Treepath Problem, Complexidade, Teoria de Grafos

Discussão: dezembro 21, 2021, 14:0