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.
Distância Geodesica, Métricas comparativas, Teoria de Grafos, Complexidade, Filogenia

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

ORIENTADOR

Pedro Alves Martins Rodrigues

Departamento de Matemática (DM)

Professor Auxiliar