软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2010年
3期
401-414
,共14页
张硕%李建中%高宏%邹兆年
張碩%李建中%高宏%鄒兆年
장석%리건중%고굉%추조년
图匹配%子图同构%预处理%图索引
圖匹配%子圖同構%預處理%圖索引
도필배%자도동구%예처리%도색인
graph matching%subgraph isomorphism%preprocessing%graph indexing
提出一种方法来解决从多个小图到一个大图的子图同构检测问题,其中多个小图是预先给定的,而大图是用户在线提交的.首先,基于DFS编码提出一种小图集合的压缩组织方法;其次,提出一种带有前向剪枝技术的从多个小图到一个大图的子图同构检测算法.另外,给出一种有效的基于数据挖掘的索引技术.分析和实验结果证实,所提出方法的在线计算代价远小于现有方法,在线执行时间比现有方法快约一个数量级,离线构造时间快一个数量级以上.
提齣一種方法來解決從多箇小圖到一箇大圖的子圖同構檢測問題,其中多箇小圖是預先給定的,而大圖是用戶在線提交的.首先,基于DFS編碼提齣一種小圖集閤的壓縮組織方法;其次,提齣一種帶有前嚮剪枝技術的從多箇小圖到一箇大圖的子圖同構檢測算法.另外,給齣一種有效的基于數據挖掘的索引技術.分析和實驗結果證實,所提齣方法的在線計算代價遠小于現有方法,在線執行時間比現有方法快約一箇數量級,離線構造時間快一箇數量級以上.
제출일충방법래해결종다개소도도일개대도적자도동구검측문제,기중다개소도시예선급정적,이대도시용호재선제교적.수선,기우DFS편마제출일충소도집합적압축조직방법;기차,제출일충대유전향전지기술적종다개소도도일개대도적자도동구검측산법.령외,급출일충유효적기우수거알굴적색인기술.분석화실험결과증실,소제출방법적재선계산대개원소우현유방법,재선집행시간비현유방법쾌약일개수량급,리선구조시간쾌일개수량급이상.
