Solving the maximum clique problem with a hybrid algorithm

Derek Smith, Stephanie Perkins, Roberto Montemanni

Research output: Contribution to journalArticlepeer-review

84 Downloads (Pure)

Abstract

A hybrid algorithm for the maximum clique problem is presented. A heuristic is used to generate cliques and these are improved by some simple optimizations and tabu search. All components of the algorithm make use of an exact algorithm or a pseudoexact algorithm, which is an exact algorithm with some specialized pruning. Preprocessing is useful for some instances. The algorithm is shown to be successful using standard and new benchmarks.
Original languageEnglish
Article numberIJMHEUR-200780
Pages (from-to)152-174
Number of pages23
JournalInternational Journal of Metaheuristics
Volume7
Issue number2
DOIs
Publication statusPublished - 1 Mar 2019

Keywords

  • Combinatorial Optimisation
  • maximum clique
  • hybrid algorithm
  • Tabu search
  • pseudoexact algorithm
  • pre-processing
  • benchmarks

Fingerprint

Dive into the research topics of 'Solving the maximum clique problem with a hybrid algorithm'. Together they form a unique fingerprint.

Cite this