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

Qinghua Wu () and Jin-Kao Hao ()
Additional contact information
Qinghua Wu: Université d’Angers
Jin-Kao Hao: Université d’Angers

Journal of Combinatorial Optimization, 2013, vol. 26, issue 1, No 7, 86-108

Abstract: 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: Tabu search; Maximum clique; Constrained neighborhood; Informed restart; Combinatorial optimization (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-011-9437-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:26:y:2013:i:1:d:10.1007_s10878-011-9437-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-011-9437-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().