一种判定树同构的BULT算法

• 作者: 梁华金 温雪莲
• 来源期刊: 中山大学学报（自然科学版）
• 学科: 工学
• 关键词: 树 树同构 时间复杂度 空间复杂度
• 年，卷（期）: 2005,（6）
• 页码范围: 24-28
• 页数: 5页
• 分类号: TP301.6
• 字数: 6270字
• 语种: 中文
• DOI: 10.3321/j.issn:0529-6579.2005.06.007

摘要

将判定两棵树的同构问题转化成"图的同构"问题和"两棵树根结点之间的对应关系"问题的判定.基于图与树的关系,提出一种自底向上分层遍历图结点(Bottom-Up Layer Traversing)的方法,简称 BULT方法,解决以上两个问题,从而得到一种线性的时间复杂度与空间复杂度的树同构判定算法,并给出了算法正确性证明.该算法很容易扩展为图同构的判定算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	梁华金	中山大学计算机科学系	9	66	4.0	8.0
2	温雪莲	中山大学计算机科学系	2	8	2.0	2.0