Improved MAX SNP-Hard Results for Finding an Edit Distances between Unordered Trees
Improved MAX SNP-Hard Results for Finding an Edit Distances between Unordered Trees
复制标题
改进了查找无序树之间编辑距离的 MAX SNP-Hard 结果
DOI：
10.1007/978-3-642-21458-5_34
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
T.Kuboyama
中科院分区：
文献类型：
--
作者：
K.Hirata;Y.Yamamoto;T.Kuboyama
张和江(1994)已经证明了无序树之间的编辑距离问题是SNP-Hard的。本文证明了当(1)树高为2，(2)树的度为2，(3)在单位成本下树的高度为3，(4)在单位成本下树的度为2的情况下，该问题是Max-SNP困难的。
Zhang and Jiang (1994) have shown that the problem offinding an edit distance between unordered treesis MAX SNP-hard. In this paper, we show that this problem is MAX SNP-hard, even if (1) the height of trees is 2, (2) the degree of trees is 2, (3) the height of trees is 3 under a unit cost, and (4) the degree of trees is 2 under a unit cost.