Solving the maximum clique problem with a hybrid algorithm

Derek Smith, Stephanie Perkins, Roberto Montemanni

    Research output: Contribution to journalArticlepeer-review

    41 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