| 摘要: |
| 提出一种方法来解决从多个小图到一个大图的子图同构检测问题,其中多个小图是预先给定的,而大图是用户在线提交的.首先,基于DFS 编码提出一种小图集合的压缩组织方法;其次,提出一种带有前向剪枝技术的从多个小图到一个大图的子图同构检测算法.另外,给出一种有效的基于数据挖掘的索引技术.分析和实验结果证实,所提出方法的在线计算代价远小于现有方法,在线执行时间比现有方法快约一个数量级,离线构造时间快一个数量级以上. |
| 关键词: 图匹配 子图同构 预处理 图索引 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Basic Research Program of China under Grant No.2006CB303005 (国家重点基础研究发展计划(973));the Key Program of the National Natural Science Foundation of China under Grant Nos.60533110, 60773063 (国家自然科学基金); the Program for New Century Excellent Talents in University of China under Grant No.NCET-05-0333 (新世纪优秀人才支持计划) |
|
| Approach for Efficient Subgraph Isomorphism Testing for Multiple Graphs |
|
ZHANG Shuo,LI Jian-Zhong,,GAO Hong,ZOU Zhao-Nian
|
| Abstract: |
| Abstract: This paper proposes an approach for subgraph isomorphism testing from a set of priori given small graphs to a large graph issued on-line. In order to reduce the computational cost,based on DFS Code,an elaborate organization of a set of graphs is presented,and a look-ahead-pruning based algorithm of subgraph isomorphism testing from multiple small graphs to a large graph is proposed.Moreover, an index technique based on data miningis introduced.Analytical and experimental results show the on-line computational cost of the proposed method is much less than the state-of-the-art method and it is about one order of magnitude faster than the existing method with more than one order of magnitude less off-line construction time. |
| Key words: graph matching subgraph isomorphism preprocessing graph indexing |
