A hybrid heuristic for the maximum clique problem

A hybrid heuristic for the maximum clique problem

0.00 Avg rating0 Votes
Article ID: iaor20062256
Country: Netherlands
Volume: 12
Issue: 1/2
Start Page Number: 5
End Page Number: 22
Publication Date: Jan 2006
Journal: Journal of Heuristics
Authors: ,
Keywords: heuristics
Abstract:

In this paper we present a heuristic based steady-state genetic algorithm for the maximum clique problem. The steady-state genetic algorithm generates cliques, which are then extended into maximal cliques by the heuristic. We compare our algorithm with three best evolutionary approaches and the overall best approach, which is non-evolutionary, for the maximum clique problem and find that our algorithm outperforms all the three evolutionary approaches in terms of best and average clique sizes found on majority of DIMACS benchmark instances. However, the obtained results are much inferior to those obtained with the best approach for the maximum clique problem.

Reviews

Required fields are marked *. Your email address will not be published.