An adaptive multistart tabu search approach to solve the maximum clique problem |
| |
Authors: | Qinghua Wu Jin-Kao Hao |
| |
Institution: | 1. LERIA, Université d’Angers, 2 Boulevard Lavoisier, 49045, Angers Cedex 01, France
|
| |
Abstract: | Given an undirected graph G=(V,E) with vertex set V={1,…,n} and edge set E?V×V. 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|