Phased Local Search for the Maximum Clique Problem

There are no files associated with this record.

Title Phased Local Search for the Maximum Clique Problem
Author Pullan, Wayne John
Journal Name Journal of Combinatorial Optimization
Year Published 2006
Place of publication Netherlands
Publisher Springer Netherlands
Abstract This paper introduces Phased Local Search (PLS), a new stochastic reactive dynamic local search algorithm for the maximum clique problem. (PLS) interleaves sub-algorithms which alternate between sequences of iterative improvement, during which suitable vertices are added to the current clique, and plateau search, where vertices of the current clique are swapped with vertices not contained in the current clique. The sub-algorithms differ in their vertex selection techniques in that selection can be solely based on randomly selecting a vertex, randomly selecting within highest vertex degree or randomly selecting within vertex penalties that are dynamically adjusted during the search. In addition, the perturbation mechanism used to overcome search stagnation differs between the sub-algorithms. (PLS) has no problem instance dependent parameters and achieves state-of-the-art performance for the maximum clique problem over a large range of the commonly used DIMACS benchmark instances.
Peer Reviewed Yes
Published Yes
Alternative URI http://dx.doi.org/10.1007/s10878-006-9635-y
Volume 12
Page from 303
Page to 323
ISSN 1573-2886
Date Accessioned 2007-03-07
Language en_AU
Faculty Faculty of Science, Environment, Engineering and Technology
Subject PRE2009-Other Artificial Intelligence
URI http://hdl.handle.net/10072/14394
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Show simple item record

Griffith University copyright notice