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.