Dissertação
An analysis of the Geodesic Distance and other comparative metrics for tree-like structures EVALUATED
Grafos são estruturas interessantes: extremamente úteis para descrever problemas da vida real, extremamente fáceis de entender dado um esboço, extremamente complicados de representar formalmente e extremamente complicados de comparar. Filogenia é o estudo das relações entre entidades biológicas. Deste, o interesse em comparar grafos árvore cresceu mais que em outros campos da ciência. Visto não existir forma definitiva de os comparar, múltiplas distâncias foram formalizadas desde o início dos anos sessenta, quando o primeiro método numérico eficaz para comparar dendogramas foi descrito. Este trabalho consiste em formalisar, completar (com trabalho original) e apresentar uma notação universal para analisar e comparar o poder discriminativo e a complexidade temporal de computar as treze métricas aqui formalizadas. Também apresentamos uma nova forma de representar grafos árvore, vamos mais fundo nos detalhes da Distância Geodésica e discutimos o pior caso de complexidade temporal numa implementação sugerida. A nossa contribuição acaba por se tornar um recurso limpo e valioso para qualquer pessoa que procure uma introdução às métricas comparativas para grafos árvore.
Dezembro 17, 2018, 11:0
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
Alexandre Paulo Lourenço Francisco
Departamento de Engenharia Informática (DEI)
Professor Associado
