A hybrid algorithm for the maximum clique problem is presented. A heuristic is used to generate cliques and these are improved by some simple optimisations 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 specialised pruning. Pre-processing is useful for some instances. The algorithm is shown to be successful using standard and new benchmarks.

Solving the maximum clique problem with a hybrid algorithm / Smith Derek, H; Perkins, Stephanie; Montemanni, Roberto. - In: INTERNATIONAL JOURNAL OF METAHEURISTICS. - ISSN 1755-2176. - 7:2(2019), pp. 152-175. [10.1504/ijmheur.2019.098270]

Solving the maximum clique problem with a hybrid algorithm

Montemanni Roberto
2019

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 optimisations 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 specialised pruning. Pre-processing is useful for some instances. The algorithm is shown to be successful using standard and new benchmarks.
2019
7
2
152
175
Solving the maximum clique problem with a hybrid algorithm / Smith Derek, H; Perkins, Stephanie; Montemanni, Roberto. - In: INTERNATIONAL JOURNAL OF METAHEURISTICS. - ISSN 1755-2176. - 7:2(2019), pp. 152-175. [10.1504/ijmheur.2019.098270]
Smith Derek, H; Perkins, Stephanie; Montemanni, Roberto
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1177088
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact