Solving the maximum clique problem with a hybrid algorithm

Derek Smith, Stephanie Perkins, Roberto Montemanni

    Research output: Contribution to journalArticlepeer-review

    77 Downloads (Pure)


    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
    Issue number2
    Publication statusPublished - 1 Mar 2019


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


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

    Cite this