论文标题
两个合并树之间的特雷希般的距离
Frechet-Like Distances between Two Merge Trees
论文作者
论文摘要
本文的目的是扩展特雷切特距离的定义，该定义可测量两条曲线之间的距离到距离（类似于特雷切特的距离），该距离测量了两棵根树之间的相似性。类似特雷切特的距离的定义如下：拖曳的人从两棵树的根源开始。当他们达到一个超过$ 2 $的节点时，他们构建了$ k-1 $ k $的$ k $是$ k $的$ k $，每个人都在另一棵树中监视一个男人（它们之间有一根绳子）。距离是男人和被监控的人之间的绳索的最小长度（它们都向前走（它们之间的地球距离与树的根部增加），并到达树木的叶子。在这里，我证明了两棵树之间的特定距离距离是SNP坚硬的距离。 我修改了类似特雷切特的距离的定义，以测量拖曳合并树之间的距离，并证明了交织距离与修改后的特雷切特距离之间的关系。
The purpose of this paper is to extend the definition of Frechet distance which measures the distance between two curves to a distance (Frechet-Like distance) which measures the similarity between two rooted trees. The definition of Frechet-Like distance is as follows: Tow men start from the roots of two trees. When they reach to a node with the degree of more than $2$, they construct $k-1$ men which $k$ is the outgoing degree of the node and each man monitor a man in another tree (there is a rope between them). The distance is the minimum length of the ropes between the men and the men whom are monitored and they all go forward (the geodesic distance between them to the root of the tree increases) and reach to the leaves of the trees. Here, I prove that the Frechet-Like distance between two trees is SNP-hard to compute. I modify the definition of Frechet-Like distance to measure the distance between tow merge trees, and I prove the relation between the interleaving distance and the modified Frechet-Like distance.
