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 | Abstract: | 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
SCOPUSTM
Citations
74
checked on Nov 11, 2024
Page view(s)
21
checked on Nov 11, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.