On computing tractable variations of unordered tree edit distance with network algorithms
On computing tractable variations of unordered tree edit distance with network algorithms
复制标题
用网络算法计算无序树编辑距离的易处理变化
DOI：
10.1007/978-3-642-32090-3_19
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
and T. Kuboyama
中科院分区：
文献类型：
--
作者：
Y. Yamamoto;K. Hirata;and T. Kuboyama
计算无序树之间的标准编辑距离的问题是众所周知的棘手。为了避免这种困难的结果，已经提出了几个易于处理的变化。这些变型的算法包括网络算法的子模块，或者是最小成本最大流算法或者是最大加权二分匹配算法。在本文中，我们指出，这些网络算法是可替换的，并给出了计算这些变化与两个网络算法的实验结果。
The problem of computing the standard edit distance between unordered trees is known to be intractable. To circumvent this hardness result, several tractable variations have been proposed. The algorithms of these variations include the submodule of a network algorithm, either the minimum cost maximum flow algorithm or the maximum weighted bipartite matching algorithm. In this paper, we point out that these network algorithms are replaceable, and give the experimental results of computing these variations with both network algorithms.