Improved approximation of the largest common subtree of two unordered trees of bounded height

被引:6
作者
Akutsu, Tatsuya [1 ]
Fukagawa, Daiji [2 ]
Takasu, Atsuhiro [2 ]
机构
[1] Kyoto Univ, Inst Chem Res, Bioinformat Ctr, Kyoto 6110011, Japan
[2] Res Org Informat & Syst, Natl Inst Informat, Tokyo 1018430, Japan
关键词
Approximation algorithms; Edit distance; Unordered trees; Common subtrees;
D O I
10.1016/j.ipl.2008.09.025
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We present a polynomial time 1.5h-approximation algorithm for the problem of finding the largest common subtree between two rooted, labeled, and unordered trees of height at most h, where a tree S is called a subtree of a tree T if S is obtained from T by deletion of some nodes in T. This result improves the previous 2h-approximation algorithm. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:165 / 170
页数:6
相关论文
共 8 条
[1]   A survey on tree edit distance and related problems [J].
Bille, P .
THEORETICAL COMPUTER SCIENCE, 2005, 337 (1-3) :217-239
[2]  
Cormen T. H., 2001, Introduction to Algorithms, V2nd
[3]  
Demaine ED, 2007, LECT NOTES COMPUT SC, V4596, P146
[4]  
Halldorsson MM, 1996, LECT NOTES COMPUT SC, V1178, P75, DOI 10.1007/BFb0009483
[5]   TREE-TO-TREE CORRECTION PROBLEM [J].
TAI, KC .
JOURNAL OF THE ACM, 1979, 26 (03) :422-433
[6]   SOME MAX SNP-HARD RESULTS CONCERNING UNORDERED LABELED TREES [J].
ZHANG, KZ ;
JIANG, T .
INFORMATION PROCESSING LETTERS, 1994, 49 (05) :249-254
[7]   ON THE EDITING DISTANCE BETWEEN UNORDERED LABELED TREES [J].
ZHANG, KZ ;
STATMAN, R ;
SHASHA, D .
INFORMATION PROCESSING LETTERS, 1992, 42 (03) :133-139
[8]  
Zhang KZ, 1996, ALGORITHMICA, V15, P205, DOI 10.1007/BF01975866