Paper Info
Title
Improved MAX SNP-hard results for finding an edit distance between unordered trees
Abstract
Zhang and Jiang (1994) have shown that the problem of finding an edit distance between unordered trees is 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.
Year
DOI
Venue
2011
10.1007/978-3-642-21458-5_34
combinatorial pattern matching
Keywords
Field
DocType
MAX SNP-hard,Improved MAX SNP-hard result,unordered tree,unit cost
Edit distance,Discrete mathematics,Combinatorics,Unit cost,Weight-balanced tree,Polynomial-time approximation scheme,Mathematics,Zhàng
Conference
Volume
ISSN
Citations 
6661
0302-9743
15
PageRank 
References 
Authors
0.72
11
3
Name
Order
Citations
PageRank
Kouichi Hirata113032.04
Yoshiyuki Yamamoto2150.72
Tetsuji Kuboyama314029.36