Simple ingredients leading to very efficient heuristics for the maximum clique problem

There are no files associated with this record.

Title Simple ingredients leading to very efficient heuristics for the maximum clique problem
Author Grosso, Andrea; Locatelli, Marco; Pullan, Wayne John
Journal Name Journal of Heuristics
Year Published 2008
Place of publication Netherlands
Publisher Springer
Abstract Starting from an algorithm recently proposed by Pullan and Hoos, we formulate and analyze iterated local search algorithms for the maximum clique problem. The basic components of such algorithms are a fast neighbourhood search (not based on node evaluation but on completely random selection) and simple, yet very effective, diversification techniques and restart rules. A detailed computational study is performed in order to identify strengths and weaknesses of the proposed algorithms and the role of the different components on several classes of instances. The tested algorithms are very fast and reliable: most of the DIMACS benchmark instances are solved within very short CPU times. For one of the hardest tests, a new putative optimum was discovered by one of our algorithms. Very good performances were also shown on recently proposed and more difficult instances. It is important to remark that the heuristics tested in this paper are basically parameter free (the appropriate value for the unique parameter is easily identified and was, in fact, the same value for all problem instances used in this paper).
Peer Reviewed Yes
Published Yes
Alternative URI
Volume 14
Issue Number 6
Page from 587
Page to 612
ISSN 1572-9397
Date Accessioned 2008-04-08
Language en_AU
Faculty Faculty of Science, Environment, Engineering and Technology
Subject PRE2009-Other Information, Computing and Communication Sciences
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Show simple item record

Griffith University copyright notice