# Elena Farahbaksh Touli: Computing interleaving distance between trees

**Time: **
Wed 2019-04-03 12.00 - 13.00

**Lecturer: **
Elena Farahbaksh Touli

**Location: **
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.