主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2018年第5期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
张硕,李建中,高宏,邹兆年.一种多到一子图同构检测方法.软件学报,2010,21(3):401-414
一种多到一子图同构检测方法
Approach for Efficient Subgraph Isomorphism Testing for Multiple Graphs
投稿时间:2008-07-17  修订日期:2008-10-09
DOI:
中文关键词:  图匹配  子图同构  预处理  图索引
英文关键词:graph matching  subgraph isomorphism  preprocessing  graph indexing
基金项目: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 (新世纪优秀人才支持计划)
作者单位
张硕 哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001 
李建中  
高宏  
邹兆年  
摘要点击次数: 5905
全文下载次数: 6505
中文摘要:
      提出一种方法来解决从多个小图到一个大图的子图同构检测问题,其中多个小图是预先给定的,而大图是用户在线提交的.首先,基于DFS 编码提出一种小图集合的压缩组织方法;其次,提出一种带有前向剪枝技术的从多个小图到一个大图的子图同构检测算法.另外,给出一种有效的基于数据挖掘的索引技术.分析和实验结果证实,所提出方法的在线计算代价远小于现有方法,在线执行时间比现有方法快约一个数量级,离线构造时间快一个数量级以上.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 
主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利