An adaptive multistart tabu search approach to solve the maximum clique problem

作者：Wu Qinghua; Hao Jin Kao^*

来源：Journal of Combinatorial Optimization, 2013, 26(1): 86-108.

DOI：10.1007/s10878-011-9437-8

• Tabu search
• Maximum clique
• Constrained neighborhood
• Informed restart
• Combinatorial optimization

Given an undirected graph G=(V,E) with vertex set V={1,aEuro broken vertical bar,n} and edge set EaS dagger VxV. The maximum clique problem is to determine in G a clique (i.e., a complete subgraph) of maximum cardinality. This paper presents an effective algorithm for the maximum clique problem. The proposed multistart tabu search algorithm integrates a constrained neighborhood, a dynamic tabu tenure mechanism and a long term memory based restart strategy. Our proposed algorithm is evaluated on the whole set of 80 DIMACS challenge benchmarks and compared with five state-of-the-art algorithms. Computational results show that our proposed algorithm attains the largest known clique for 79 benchmarks.

• 出版日期2013-7