Simulated annealing algorithm for detecting graph isomorphism  

作　　者：Geng Xiutang Zhang Kai 

机构地区：[1]Dept. of Control Science and Engineering, Huazhong Univ. of Science and Technology, Wuhan 430074, P. R. China

出　　处：《Journal of Systems Engineering and Electronics》2008年第5期1047-1052,共6页系统工程与电子技术（英文版）

基　　金：the National Natural Science Foundation of China (60373089, 60674106, and 60533010);the National High Technology Research and Development "863" Program (2006AA01Z104)

摘　　要：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.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.

关 键 词：graph isomorphism problem simulated annealing algorithm nondeterministic polynomial problem local search. 

分 类 号：TH11[机械工程—机械设计及理论]