TY - JOUR
ID - 81145
TI - Fr'echet-Like Distances between Two Rooted Trees
JO - Journal of Algorithms and Computation
JA - JAC
LA - en
SN - 2476-2776
AU - Farahbakhsh Touli, Elena
AD - Stockholm University, Department of Mathematics
Y1 - 2021
PY - 2021
VL - 53
IS - 1
SP - 1
EP - 12
KW - Merge trees
KW - Fr'echet distance
KW - Fr'echet-Like distance
KW - modified Fr'echet-Like distance
KW - interleaving distance
DO -
N2 - 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.
UR - https://jac.ut.ac.ir/article_81145.html
L1 - https://jac.ut.ac.ir/article_81145_9cd801c5f8020bd4f3d182de4877a405.pdf
ER -