Simulated annealing algorithm for detecting graph isomorphism*

Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem (GIP) is a nondeterministic polynomial problem. A simulated annealing (SA) algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.