Fr\'echet-Like Distances between Two Rooted Trees

Document Type : Research Paper


Stockholm University, Department of Mathematics


The purpose of this paper is to extend the definition of Fr'echet distance which measures the distance between two curves to a distance (Fr'echet-Like distance) which measures the similarity between two rooted trees.
In this paper, I prove that the Fr'echet-Like distance between two trees is SNP-hard to compute.
Later, I modify the definition of Fr'echet-Like distance to measure the distance between two merge trees, and I prove the relation between the interleaving distance and the modified Fr'echet-Like distance.