扩展子图同构问题的优化算法

• 作者: 徐凯旋 鲁道夫
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 图数据库 AIDS数据库 Ullmann算法 扩展子图同构 动态加边算法
• 年，卷（期）: 2011,（19）
• 所属期刊栏目: 软件技术与数据库
• 页码范围: 38-40
• 分类号: TN919.81
• 字数: 4447字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2011.19.011

摘要

针对扩展子图的匹配问题,根据Ullmann剪枝和QuickSI的不同特性,提出优化处理距离信息的加边算法.根据Query中各个顶点到不同label顶点的最短距离进行剪枝,采用动态加边算法减少加边的运算时间,能够处理规模不大的稀疏图.在AIDS数据库上的实验结果表明,在不同距离值的条件下,QuickSI算法的平均运行速度比Ullmann算法快一个数量级以上.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐凯旋	复旦大学计算机科学学院智能信息处理实验室	1	2	1.0	1.0
2	鲁道夫	复旦大学计算机科学学院智能信息处理实验室	1	2	1.0	1.0