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

Grŵp Ymchwil ac Arloesi Cyfrifiadureg, Seiberddiogelwch, Mathemateg a Gwybodeg

Allbwn ymchwil: Cyfraniad at gyfnodolyn › Erthygl › adolygiad gan gymheiriaid

127 Wedi eu Llwytho i Lawr (Pure)

Crynodeb

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.

Iaith wreiddiol	Saesneg
Rhif yr erthygl	IJMHEUR-200780
Tudalennau (o-i)	152-174
Nifer y tudalennau	23
Cyfnodolyn	International Journal of Metaheuristics
Cyfrol	7
Rhif cyhoeddi	2
Dynodwyr Gwrthrych Digidol (DOIs)	https://doi.org/10.1504/IJMHEUR.2019.10019620
Statws	Cyhoeddwyd - 1 Maw 2019

Mynediad at Ddogfen

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

SmithMontemanniPerkins_IJMh_preprintLlawysgrif awdur wedi’i dderbyn, 121 KBTrwydded: CC BY-NC

Dyfynnu hyn

@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

Crynodeb

Mynediad at Ddogfen

Ôl bys

Dyfynnu hyn