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.
Farahbakhsh Touli, E. (2021). Fr\'echet-Like Distances between Two Rooted Trees. Journal of Algorithms and Computation, 53(1), 1-12. doi: 10.22059/jac.2021.81145
MLA
Elena Farahbakhsh Touli. "Fr\'echet-Like Distances between Two Rooted Trees". Journal of Algorithms and Computation, 53, 1, 2021, 1-12. doi: 10.22059/jac.2021.81145
HARVARD
Farahbakhsh Touli, E. (2021). 'Fr\'echet-Like Distances between Two Rooted Trees', Journal of Algorithms and Computation, 53(1), pp. 1-12. doi: 10.22059/jac.2021.81145
VANCOUVER
Farahbakhsh Touli, E. Fr\'echet-Like Distances between Two Rooted Trees. Journal of Algorithms and Computation, 2021; 53(1): 1-12. doi: 10.22059/jac.2021.81145
)