• 中国期刊全文数据库
  • 中国学术期刊综合评价数据库
  • 中国科技论文与引文数据库
  • 中国核心期刊(遴选)数据库
王嘉鑫, 徐周波, 龙广兴. 基于新过滤技术的子图匹配符号ADD算法J. 桂林电子科技大学学报, 2026, 46(4): 348-353. DOI: 10.16725/j.1673-808X.2023123
引用本文: 王嘉鑫, 徐周波, 龙广兴. 基于新过滤技术的子图匹配符号ADD算法J. 桂林电子科技大学学报, 2026, 46(4): 348-353. DOI: 10.16725/j.1673-808X.2023123
Wang Jiaxin, Xu Zhoubo, Long Guangxing. Symbolic ADD algorithm for subgraph matching based on new filtering techniquesJ. Journal of Guilin University of Electronic Technology, 2026, 46(4): 348-353. DOI: 10.16725/j.1673-808X.2023123
Citation: Wang Jiaxin, Xu Zhoubo, Long Guangxing. Symbolic ADD algorithm for subgraph matching based on new filtering techniquesJ. Journal of Guilin University of Electronic Technology, 2026, 46(4): 348-353. DOI: 10.16725/j.1673-808X.2023123

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

Symbolic ADD algorithm for subgraph matching based on new filtering techniques

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

     

    Abstract: 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 incorporating a new filtering technique. To improve the pruning efficiency of candidate sets for query vertices, a compressed storage structure is constructed by integrating the symbolic algebraic decision diagram (ADD) structure with the CS structure used in the DAF algorithm. In addition, a new candidate filtering technique, termed DDFilter, is developed by introducing k-field aggregation constraints. Experimental results demonstrate that DDCSA significantly improves the efficiency of subgraph isomorphism computation compared with the DAF algorithm.

     

/

返回文章
返回