A hybrid heuristic for the maximum clique problem |
| |
Authors: | Alok Singh Ashok Kumar Gupta |
| |
Institution: | (1) J. K. Institute of Applied Physics and Technology, Faculty of Science, University of Allahabad, Allahabad, 211002, UP, India |
| |
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. |
| |
Keywords: | Combinatorial optimization Greedy heuristic Maximum clique Steady-state genetic algorithm |
本文献已被 SpringerLink 等数据库收录! |
|