Authors: Hansen, Pierre
Mladenović, Nenad 
Urošević, Dragan 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Variable neighborhood search for the maximum clique
Journal: Discrete Applied Mathematics
Volume: 145
Issue: 1 SPEC. ISS.
First page: 117
Last page: 125
Issue Date: 30-Dec-2004
Rank: M22
ISSN: 0166-218X
DOI: 10.1016/j.dam.2003.09.012
Maximum clique is one of the most studied NP-hard optimization problem on graphs because of its simplicity and its numerous applications. A basic variable neighborhood search heuristic for maximum clique that combines greedy with the simplicial vertex test in its descent step is proposed and tested on standard test problems from the literature. Despite its simplicity, the proposed heuristic outperforms most of the well-known approximate solution methods. Moreover, it gives solution of equal quality to those of the state-of-the-art heuristic of Battiti and Protasi in half the time.
Keywords: Combinatorial optimization | Graphs | Heuristics | Maximum clique | Variable neighborhood search
Publisher: Elsevier

Show full item record


checked on Jun 12, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.