An Improved Heuristic Method for Subgraph Isomorphism Problem

2017 2nd International Seminar on Advances in Materials Science and Engineering

Xiang, Yingzhuo^1 ; Han, Jiesi^1 ; Xu, Haijiang^2 ; Guo, Xin^3

National Key Laboratory of Science and Technology on Blind Signal Processing, Chengdu, China^1

Jiangnan Institute of Computing Technology, Wuxi, China^2

School of Mathematical Sciences of UESTC, Chengdu, China^3

关键词: Evolution process;    Fitness functions;    Large graphs;    Optimal solutions;    Subgraph isomorphism;    Subgraph isomorphism problem;    Subgraphs;    Tree search algorithm;   

Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/231/1/012050/pdf
DOI  :  10.1088/1757-899X/231/1/012050

来源: IOP

【 摘 要 】

This paper focus on the subgraph isomorphism (SI) problem. We present an improved genetic algorithm, a heuristic method to search the optimal solution. The contribution of this paper is that we design a dedicated crossover algorithm and a new fitness function to measure the evolution process. Experiments show our improved genetic algorithm performs better than other heuristic methods. For a large graph, such as a subgraph of 40 nodes, our algorithm outperforms the traditional tree search algorithms. We find that the performance of our improved genetic algorithm does not decrease as the number of nodes in prototype graphs.