Optimization Online


A Simple Clique Camouflaging Against Greedy Maximum Clique Heuristics

Stanislav Busygin (busygin***at***a-teleport.com)

Abstract: Taking a small graph, on which the randomized New-Best-In maximum clique heuristic fails to find the maximum clique, we construct on its basis a class of graphs exemplifying the inefficiency of SM greedy heuristics considered by Brockington and Culberson. We show that a 7(k+1)-vertex graph from this class is enough to provide a counterexample for the SM^k heuristic. On the other hand, two recent continuous heuristics -- Max-AO and QUALEX-MS -- successfully find exact solutions on the considered graphs.

Keywords: maximum clique, greedy heuristics, forbidden subgraphs, continuous approach, algorithms, NP-hard

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: Stas Busygin's NP-Completeness Page (http://www.busygin.dp.ua/npc.html), 2002.

Download: [Postscript][Compressed Postscript]

Entry Submitted: 12/19/2002
Entry Accepted: 12/22/2002
Entry Last Modified: 12/19/2002

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society