首页|期刊导航|桂林电子科技大学学报|基于新过滤技术的子图匹配符号ADD算法

基于新过滤技术的子图匹配符号ADD算法OA

Symbolic ADD algorithm for subgraph matching based on new filtering techniques

中文摘要英文摘要

子图匹配问题是 NP 完全问题,在计算机视觉、数据挖掘、生物信息学等领域得到广泛应用.针对子图匹配求解过程中大量冗余计算出现的问题,提出一种基于新的过滤技术的子图匹配算法 DDCSA.为提高各查询节点候选集的修剪效率,将符号 ADD 结构与 DAF 算法中的 CS 结构相融合,构建全新压缩存储结构,同时通过引入 k 域聚合约束,提出了一种新的候选集过滤技术 DDFilter.最后,对比子图匹配算法 DDCSA 与 DAF 算法,该算法有效地提高了子图同构的求解效率.

Subgraph matching is a fundamental NP-complete problem with broad applications in computer vision,data mining,and bioinformatics.To reduce redundant computations in subgraph matching,a novel algorithm named DDCSA is proposed by incorpo-rating a new filtering technique.To improve the pruning efficiency of candidate sets for query vertices,a compressed storage struc-ture is constructed by integrating the symbolic algebraic decision diagram(ADD)structure with the CS structure used in the DAF al-gorithm.In addition,a new candidate filtering technique,termed DDFilter,is developed by introducing k-field aggregation con-straints.Experimental results demonstrate that DDCSA significantly improves the efficiency of subgraph isomorphism computation compared with the DAF algorithm.

王嘉鑫;徐周波;龙广兴

桂林电子科技大学 计算机与信息安全学院,广西 桂林 541004桂林电子科技大学 计算机与信息安全学院,广西 桂林 541004桂林电子科技大学 计算机与信息安全学院,广西 桂林 541004

信息技术与安全科学

图匹配问题子图匹配过滤技术代数决策图(ADD)辅助结构

graph matching problemsubgraph matchingfiltering techniquealgebraic decision diagram(ADD)auxiliary structure

《桂林电子科技大学学报》 2026 (4)

348-353,371,7

国家自然科学基金(61762027)

10.16725/j.1673-808X.2023123

评论