首页 | 本学科首页   官方微博 | 高级检索  
     

一种多到一子图同构检测方法
引用本文:张硕,李建中,高宏,邹兆年.一种多到一子图同构检测方法[J].软件学报,2010,21(3):401-414.
作者姓名:张硕  李建中  高宏  邹兆年
作者单位:哈尔滨工业大学,计算机科学与技术学院,黑龙江,哈尔滨,150001
基金项目: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 (新世纪优秀人才支持计划)
摘    要:提出一种方法来解决从多个小图到一个大图的子图同构检测问题,其中多个小图是预先给定的,而大图是用户在线提交的.首先,基于DFS 编码提出一种小图集合的压缩组织方法;其次,提出一种带有前向剪枝技术的从多个小图到一个大图的子图同构检测算法.另外,给出一种有效的基于数据挖掘的索引技术.分析和实验结果证实,所提出方法的在线计算代价远小于现有方法,在线执行时间比现有方法快约一个数量级,离线构造时间快一个数量级以上.

关 键 词:图匹配  子图同构  预处理  图索引
收稿时间:2008/7/17 0:00:00
修稿时间:2008/10/9 0:00:00

Approach for Efficient Subgraph Isomorphism Testing for Multiple Graphs
ZHANG Shuo,LI Jian-Zhong,GAO Hong and ZOU Zhao-Nian.Approach for Efficient Subgraph Isomorphism Testing for Multiple Graphs[J].Journal of Software,2010,21(3):401-414.
Authors:ZHANG Shuo  LI Jian-Zhong  GAO Hong and ZOU Zhao-Nian
Affiliation:ZHANG Shuo+,LI Jian-Zhong,GAO Hong,ZOU Zhao-Nian (School of Computer Science , Technology,Harbin Institute of Technology,Harbin 150001,China)
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.
Keywords:graph matching  subgraph isomorphism  preprocessing  graph indexing
本文献已被 CNKI 万方数据 等数据库收录!
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号