A simple simulated annealing algorithm for the maximum clique problem

被引：56

作者：

Geng, Xiutang ^{[1
]}

Xu, Jin ^{[1
]}

Xiao, Jianhua ^{[1
]}

Pan, Linqiang ^{[1
]}

机构：

[1] Huazhong Univ Sci & Technol, Dept Control Sci & Engn, Key Lab Image Proc & Intelligent Control, Wuhan 430074, Peoples R China

来源：

INFORMATION SCIENCES | 2007年 / 177卷 / 22期

基金：

中国国家自然科学基金;

关键词：

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

D O I：

10.1016/j.ins.2007.06.009

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. (C) 2007 Elsevier Inc. All rights reserved.

引用

页码：5064 / 5071

页数：8

共 23 条

[1]

[Anonymous], 1987, SIMULATED ANNEALING

[2] FINDING A MAXIMUM CLIQUE IN AN ARBITRARY GRAPH [J].