Bom dia a todos,

Teremos no dia 17 de Dezembro, segunda-feira, pelas 11:00, na sala P3,
IST Alameda, a apresentação e discussão da tese de mestrado do Bernardo
Lopo Fernandes, "An analysis of the Geodesic Distance and other
comparative metrics for tree-like structures".

Abstract: Graphs are interesting structures: extremely useful to depict
real life problems, extremely easy to understand given a sketch,
extremely complicated to represent formally, extremely complicated to
compare. Phylogeny is the study of the relations between biological
entities. From it, the interest in comparing tree graphs grew more than
in other fields of science. Since there is no definitive way to compare
them, multiple distances were formalised over the years since the early
sixties, when the first effective numerical method to compare dendrograms
was described. This work consists in formalising, completing (with
original work) and give an universal notation to analyse and compare the
discriminatory power and time complexity of computing the thirteen here
formalised metrics. We also present a new way to represent tree graphs,
reach deeper in the details of the Geodesic Distance and discuss its
worst case time complexity in a suggested implementation. Our
contribution ends up as a clean, valuable resource for anyone looking
for an introduction to comparative metrics for tree graphs.

Saudações,

Alexandre Francisco