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

Derek H. Smith, Roberto Montemanni, Stephanie Perkins

Allbwn ymchwil: Cyfraniad at gyfnodolynErthygladolygiad gan gymheiriaid

27 Wedi eu Llwytho i Lawr (Pure)

Crynodeb

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.
Iaith wreiddiolSaesneg
Rhif yr erthygl253
CyfnodolynAlgorithms
Cyfrol13
Rhif cyhoeddi10
Dyddiad ar-lein cynnar4 Hyd 2020
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsE-gyhoeddi cyn argraffu - 4 Hyd 2020

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn