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

摘要：

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

关键词：图数据库、AIDS数据库、Ullmann算法、扩展子图同构、动态加边算法

所属期刊栏目：37

分类号：TN919.81

资助基金：国家自然科学基金资助项目60973026;上海市教委重点学科基金资助项目B114;上海市科学技术委员会基金资助项目08DZ2271800,09DZ2272800

在线出版日期：2012-02-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：38-40