Approximating the maximum vertex/edge weighted clique using local search

There are no files associated with this record.

Title Approximating the maximum vertex/edge weighted clique using local search
Author Pullan, Wayne John
Journal Name Journal of Heuristics
Year Published 2008
Place of publication Netherlands
Publisher Springer
Abstract This paper extends the recently introduced Phased Local Search (PLS) algorithm to more difficult maximum clique problems and also adapts the algorithm to handle maximum vertex/edge weighted clique instances. PLS is a stochastic reactive dynamic local search algorithm that interleaves sub-algorithms which alternate between sequences of iterative improvement, during which suitable vertices are added to the current sub-graph, and plateau search, where vertices of the current sub-graph are swapped with vertices not contained in the current sub-graph. These sub-algorithms differ in firstly their vertex selection techniques in that selection can be solely based on randomly selecting a vertex, randomly selecting within highest vertex degree, or random selecting within vertex penalties that are dynamically adjusted during the search. Secondly, 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 maximum clique and maximum vertex/edge weighted clique problems over a large range of the commonly used DIMACS benchmark instances.
Peer Reviewed Yes
Published Yes
Alternative URI http://dx.doi.org/10.1007/s10732-007-9026-2
Volume 14
Issue Number 2
Page from 117
Page to 134
ISSN 1572-9397
Date Accessioned 2008-04-08
Date Available 2009-09-16T07:43:27Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject PRE2009-Other Information, Computing and Communication Sciences
URI http://hdl.handle.net/10072/18582
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Brief Record

Griffith University copyright notice