摘要: 针对扩展子图的匹配问题,根据Ullmann剪枝和QuickSI的不同特性,提出优化处理距离信息的加边算法。根据Query中各个顶点到不同label顶点的最短距离进行剪枝,采用动态加边算法减少加边的运算时间,能够处理规模不大的稀疏图。在AIDS数据库上的实验结果表明,在不同距离值的条件下,QuickSI算法的平均运行速度比Ullmann算法快一个数量级以上。
中图分类号:
徐凯旋, 鲁道夫. 扩展子图同构问题的优化算法[J]. 计算机工程, 2011, 37(19): 38-40.
XU Kai-Xuan, LU Dao-Fu. Optimized Algorithm of Extended Subgraph Isomorphism Problem[J]. Computer Engineering, 2011, 37(19): 38-40.