Elena Farahbaksh Touli: Computing interleaving distance between trees

Tid: On 2019-04-03 kl 12.00 - 13.00

Föreläsare: Elena Farahbaksh Touli

Plats: Room 16, in house 5, SU

Finding the distance between trees, to understand how similar two
trees are, has become a controversial topic among scientists and has
attracted a lot of attention. In this seminar I will talk about
several well-known distance metrics between some classes of trees and
discuss their pros and cons. Interleaving distance is one of the
distances which is defined between merge trees. I will also present
another definition for finding the interleaving distance between merge
trees, and a polynomial time algorithm for computing the interleaving
distance between specific merge trees. This in turn leads to a
polynomial time algorithm for computing the Gromov-Hausdorff distance.
Gromov-Hausdorff distance is defined between metric spaces to indicate
their distance from being isometric. It has been proven that the
approximating of the Gromov-Hausdorff distance between two metric
trees (even trees with unit edge length) within a factor of 3 is NP-hard.