Dynamic Local Search for the Maximum Clique Problem

File Size Format
40530_1.pdf 458Kb Adobe PDF View
Title Dynamic Local Search for the Maximum Clique Problem
Author Pullan, Wayne John; Hoos, Holger H.
Journal Name Journal of Artificial Intelligence Research
Year Published 2006
Place of publication USA
Publisher AI Access Foundation
Abstract In this paper, we introduce DLS-MC, a new stochastic local search algorithm for the maximum clique problem. DLS-MC alternates between phases of iterative improvement, during which suitable vertices are added to the current clique, and plateau search, during which vertices of the current clique are swapped with vertices not contained in the current clique. The selection of vertices is solely based on vertex penalties that are dynamically adjusted during the search, and a perturbation mechanism is used to overcome search stagnation. The behaviour of DLS-MC is controlled by a single parameter, penalty delay, which controls the frequency at which vertex penalties are reduced. We show empirically that DLSMC achieves substantial performance improvements over state-of-the-art algorithms for the maximum clique problem over a large range of the commonly used DIMACS benchmark instances.
Peer Reviewed Yes
Published Yes
Publisher URI http://www.jair.org/
Copyright Statement Copyright 2006 A I Access Foundation, Inc. The attached file is reproduced here in accordance with the copyright policy of the publisher. Please refer to the journal's website for access to the definitive, published version.
Volume 25
Page from 159
Page to 185
ISSN 1076-9757
Date Accessioned 2007-03-07
Date Available 2008-02-19T06:03:39Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Other Artificial Intelligence
URI http://hdl.handle.net/10072/14393
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Brief Record

Griffith University copyright notice