A simple simulated annealing algorithm for the maximum clique problem

作者：Geng Xiutang^*; Xu Jin; Xiao Jianhua; Pan Linqiang

来源：Information Sciences, 2007, 177(22): 5064-5071.

DOI：10.1016/j.ins.2007.06.009

• simulated annealing algorithm
• maximum clique problem
• minimum vertex cover problem
• NP-hard optimization problem
• heuristic algorithm

Simulated annealing technique has mostly been used to solve various optimization and learning problems, and it is well known that the maximum clique problem is one of the most studied NP-hard optimization problems owing to its numerous applications. In this note, a simple simulated annealing algorithm for the maximum clique problem is proposed and tested on all 80 DIMACS maximum clique instances. Although it is simple, the proposed simulated annealing algorithm is efficient on most of the DIMACS maximum clique instances. The simulation results show that the proposed simulated annealing algorithm outperforms a recent efficient simulated annealing algorithm proposed by Xu and Ma, and the solutions obtained by the proposed simulated annealing algorithm have the equal quality with those obtained by a recent trust region heuristic algorithm of Stanislav Busygin.

• 出版日期2007-11-15
• 单位华中科技大学