An algorithm for finding a representation of a subtree distance
An algorithm for finding a representation of a subtree distance
复制标题
一种查找子树距离表示的算法
DOI：
10.1007/s10878-017-0145-x
复制
发表时间：
2018
影响因子：
1
通讯作者：
Sato Koki
中科院分区：
文献类型：
--
作者：
Ando Kazutoshi;Sato Koki
Hirai（Ann Combinatorics 10：111-128，2006）推广了树度量的概念，引入了子树距离的概念。一个非负值映射称为子树距离，如果存在一个加权树T和一个由X中的元素索引的T的子树族，使得，其中是和之间的距离。Hirai（2006）提供了对应于Buneman（J ComB Theory，Series B 17：48-50，1974）的树度量的四点条件的子树距离的表征。利用这个特征，我们可以判断一个给定的映射是否是Otime中的子树距离。在本文中，我们展示了一个Otime算法，找到一个表示一个给定的子树距离。这就产生了一个Otime算法来决定一个给定的映射是否是一个子树距离。
Generalizing the concept of tree metric, Hirai (Ann Combinatorics 10:111–128, 2006) introduced the concept of subtree distance. A nonnegative-valued mappingis called a subtree distance if there exist a weighted treeTand a familyof subtrees ofTindexed by the elements inXsuch that, whereis the distance betweenandinT. Hirai (2006) provided a characterization of subtree distances that corresponds to Buneman’s (J Comb Theory, Series B 17:48–50, 1974) four-point condition for tree metrics. Using this characterization, we can decide whether or not a given mapping is a subtree distance in Otime. In this paper, we show an Otime algorithm that finds a representation of a given subtree distance. This results in an Otime algorithm for deciding whether a given mapping is a subtree distance.