Let G = (V, E) be an undirected graph with vertex set V and edge set E. A clique C of G is a subset of the vertices of V with every pair of vertices of C adjacent. A maximum clique is a clique with the maximum number of vertices. A tabu search algorithm for the maximum clique problem that uses an exact algorithm on subproblems is presented. The exact algorithm uses a graph coloring upper bound for pruning, and the best such algorithm to use in this context is considered. The final tabu search algorithm successfully finds the optimal or best known solution for all standard benchmarks considered. It is compared with a state-of-the-art algorithm that does not use exact search. It is slower to find the known optimal solution for most instances but is faster for five instances and finds a larger clique for two instances.

The Use of an Exact Algorithm Within a Tabu Search Maximum Clique Algorithm / Smith, Derek H.; Montemanni, Roberto; Perkins, Stephanie. - In: ALGORITHMS. - ISSN 1999-4893. - 13:10(2020), pp. 253-253. [10.3390/a13100253]

The Use of an Exact Algorithm Within a Tabu Search Maximum Clique Algorithm

Roberto Montemanni;
2020

Abstract

Let G = (V, E) be an undirected graph with vertex set V and edge set E. A clique C of G is a subset of the vertices of V with every pair of vertices of C adjacent. A maximum clique is a clique with the maximum number of vertices. A tabu search algorithm for the maximum clique problem that uses an exact algorithm on subproblems is presented. The exact algorithm uses a graph coloring upper bound for pruning, and the best such algorithm to use in this context is considered. The final tabu search algorithm successfully finds the optimal or best known solution for all standard benchmarks considered. It is compared with a state-of-the-art algorithm that does not use exact search. It is slower to find the known optimal solution for most instances but is faster for five instances and finds a larger clique for two instances.
2020
13
10
253
253
The Use of an Exact Algorithm Within a Tabu Search Maximum Clique Algorithm / Smith, Derek H.; Montemanni, Roberto; Perkins, Stephanie. - In: ALGORITHMS. - ISSN 1999-4893. - 13:10(2020), pp. 253-253. [10.3390/a13100253]
Smith, Derek H.; Montemanni, Roberto; Perkins, Stephanie
File in questo prodotto:
File Dimensione Formato  
algorithms-13-00253-v2.pdf

Open access

Tipologia: Versione pubblicata dall'editore
Dimensione 247.03 kB
Formato Adobe PDF
247.03 kB Adobe PDF Visualizza/Apri
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/1211455
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 6
social impact