基于新过滤技术的子图匹配符号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)
评论