A constrained edit distance between unordered labeled trees

被引:9
作者
Zhang, KZ
机构
关键词
unordered trees; constrained edit distance; approximate tree matching;
D O I
暂无
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
This paper considers the problem of computing a constrained edit distance between unordered labeled trees. The problem of approximate unordered tree matching is also considered. We present dynamic programming algorithms solving these problems in sequential time O(\T-1\ x \T-2\ x (deg(T-1) + deg(T-2)) x log(2)(deg(T-1) + deg(T-2))). Our previous result shows that computing the edit distance between unordered labeled trees is NP-complete.
引用
收藏
页码:205 / 222
页数:18
相关论文
共 19 条
[1]  
ARORA S, 1992, AN S FDN CO, P14
[2]  
KILPELAINEN P, 1991, P INT JOINT C THEORY, V1, P202
[3]   FAST PARALLEL AND SERIAL APPROXIMATE STRING MATCHING [J].
LANDAU, GM ;
VISHKIN, U .
JOURNAL OF ALGORITHMS, 1989, 10 (02) :157-169
[4]  
MASUYAMA S, 1990, LARGEST COMMON SUBGR, P195
[5]  
Sellers PH., 1980, J. Algorithms, V1, P359, DOI [DOI 10.1016/0196-6774(80)90016-4, 10.1016/0196-6774(80)90016-4.1, DOI 10.1016/0196-6774(80)90016-4.1]
[6]  
SHAPIRO BA, 1990, COMPUT APPL BIOSCI, V6, P309
[7]  
Shih F. Y., 1991, Journal of Systems Integration, V1, P235, DOI 10.1007/BF02426925
[8]   THRESHOLD DECOMPOSITION OF GRAY-SCALE MORPHOLOGY INTO BINARY MORPHOLOGY [J].
SHIH, FYC ;
MITCHELL, OR .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1989, 11 (01) :31-42
[9]   TREE-TO-TREE CORRECTION PROBLEM [J].
TAI, KC .
JOURNAL OF THE ACM, 1979, 26 (03) :422-433
[10]  
TAKAHASHI Y, 1987, ANAL SCI, V3, P23