Efficient Exponential Time Algorithms for Edit Distance between Unordered Trees
Efficient Exponential Time Algorithms for Edit Distance between Unordered Trees
复制标题
无序树间编辑距离的高效指数时间算法
DOI：
10.1007/978-3-642-31265-6_29
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Atsuhiro Takasu
中科院分区：
文献类型：
--
作者：
Tatsuya Akutsu;Takeyuki Tamura;Daiji Fukagawa;Atsuhiro Takasu
本文提出了一种有效的指数时间算法来解决无序树编辑距离问题，这是已知的NP-难。在一般情况下，给出了一个时间算法，其中1和n2是两个输入树的节点数。该算法结合了动态规划、穷举搜索和最大加权二部匹配等技术。对于固定字母表上的有界度树，证明了对于任意固定的ε> 0，该问题都能及时解.这个结果是通过避免重复计算相同的子集的小子树。
This paper presents efficient exponential time algorithms for the unordered tree edit distance problem, which is known to be NP-hard. For a general case, antime algorithm is presented, wheren1andn2are the numbers of nodes in two input trees. This algorithm is obtained by a combination of dynamic programming, exhaustive search, and maximum weighted bipartite matching. For bounded degree trees over a fixed alphabet, it is shown that the problem can be solved intime for any fixedε> 0. This result is achieved by avoiding duplicate calculations for identical subsets of small subtrees.
DOI：
10.1007/bfb0009483
发表时间：
1996
期刊：
--
影响因子：
--
作者：
M. Halldórsson;Keisuke Tanaka
通讯作者：
Keisuke Tanaka
影响因子：
1.1
作者：
S. Canzar;Khaled M. Elbassioni;G. Klau;Julián Mestre
通讯作者：
Julián Mestre