两棵树的公共子树查找算法综述

被引：4

作者：

晁晓菲 ^{[1
]}

杨晓龙 ^{[2
]}

李书琴 ^{[1
]}

唐晶磊 ^{[1
]}

机构：

[1] 西北农林科技大学信息工程学院

[2] 西安航空技术高等专科学校机械工程系

来源：

陕西理工学院学报(自然科学版) | 2009年 / 25卷 / 02期

关键词：

最大公共子树; 后缀树; 平衡串; 枚举树; 最大公共子图;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

本文通过对基于两棵树中的公共子树查找问题在有根、带标记、有序树中的主要算法及相关历史的回顾,结合算法思想将公共子树查找问题分为主要3类。本文深入探讨了每类算法中的代表算法,其中根据数据挖掘中枚举树相关技术提出了一种可能的公共子树查找算法的思想。最后比较了文中主要算法的效率,同时较为深入地分析和讨论了公共子树的相关研究及未来可能的研究发展方向。

引用

页码：33 / 39

页数：7

共 14 条

[1]

一种分割平面简单多边形的高效算法 [J].

韩瑜 ;

张正峰 .

陕西理工学院学报(自然科学版), 2009, 25 (01) :47-50

[2]

基于邻接表分解自相交折线的算法设计 [J].

韩瑜 ;

张正峰 .

陕西理工学院学报(自然科学版), 2008, (04) :42-44

[3]

垂直搜索在电子商务中的应用分析 [J].

周作涛 .

陕西理工学院学报(自然科学版), 2008, (03) :41-44

[4]

一种保持图像细节的自适应的去噪平滑算法 [J].

唐世伟 ;

何雷 ;

李明 ;

谢芳 .

陕西理工学院学报(自然科学版), 2008, (01) :62-64+72

[5]

基于VPRS的ID3算法改进 [J].

张瑞玲 ;

都彦格 ;

张克勇 .

陕西理工学院学报(自然科学版), 2007, (03) :38-41+54

[6]

一种基于最优近邻交叉的遗传算法 [J].

田斐 ;

崔世林 .

陕西理工学院学报(自然科学版), 2007, (02) :25-28+37

[7]

Maximum common subgraph isomorphism algorithms for the matching of chemical structures [J].

Raymond, JW ;

Willett, P .

JOURNAL OF COMPUTER-AIDED MOLECULAR DESIGN, 2002, 16 (07) :521-533

[8]

Enumerating all connected maximal common subgraphs in two graphs.[J].Ina Koch.Theoretical Computer Science.2001, 1

[9]

On the approximation of largest common subtrees and largest common point sets.[J].Tatsuya Akutsu;Magnús M. Halldórsson.Theoretical Computer Science.2000, 1

[10]

Faster subtree isomorphism [J].

Shamir, R ;

Tsur, D .

JOURNAL OF ALGORITHMS, 1999, 33 (02) :267-280

← 1 2 →