Solving the maximum clique problem with a hybrid algorithm

Derek Smith; Stephanie Perkins; Roberto Montemanni

doi:10.1504/IJMHEUR.2019.10019620

Solving the maximum clique problem with a hybrid algorithm

Derek Smith, Stephanie Perkins, Roberto Montemanni

Computing, Cybersecurity, Mathematics and Informatics Research and Innovation Group

Research output: Contribution to journal › Article › peer-review

134 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 language	English
Article number	IJMHEUR-200780
Pages (from-to)	152-174
Number of pages	23
Journal	International Journal of Metaheuristics
Volume	7
Issue number	2
DOIs	https://doi.org/10.1504/IJMHEUR.2019.10019620
Publication status	Published - 1 Mar 2019

Keywords

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

Access to Document

10.1504/IJMHEUR.2019.10019620Licence: CC BY-NC-ND

SmithMontemanniPerkins_IJMh_preprintAccepted author manuscript, 121 KBLicence: CC BY-NC

Cite this

@article{928610a9d0684054a3a8226f26e54bff,

title = "Solving the maximum clique problem with a hybrid algorithm",

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.",

keywords = "Combinatorial Optimisation, maximum clique, hybrid algorithm, Tabu search, pseudoexact algorithm, pre-processing, benchmarks",

author = "Derek Smith and Stephanie Perkins and Roberto Montemanni",

year = "2019",

month = mar,

day = "1",

doi = "10.1504/IJMHEUR.2019.10019620",

language = "English",

volume = "7",

pages = "152--174",

journal = "International Journal of Metaheuristics",

issn = "1755-2176",

publisher = "Inderscience",

number = "2",

}

TY - JOUR

T1 - Solving the maximum clique problem with a hybrid algorithm

AU - Smith, Derek

AU - Perkins, Stephanie

AU - Montemanni, Roberto

PY - 2019/3/1

Y1 - 2019/3/1

N2 - 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.

AB - 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.

KW - Combinatorial Optimisation

KW - maximum clique

KW - hybrid algorithm

KW - Tabu search

KW - pseudoexact algorithm

KW - pre-processing

KW - benchmarks

U2 - 10.1504/IJMHEUR.2019.10019620

DO - 10.1504/IJMHEUR.2019.10019620

M3 - Article

SN - 1755-2176

VL - 7

SP - 152

EP - 174

JO - International Journal of Metaheuristics

JF - International Journal of Metaheuristics

IS - 2

M1 - IJMHEUR-200780

ER -

Solving the maximum clique problem with a hybrid algorithm

Abstract

Keywords

Access to Document

Fingerprint

Cite this