A Simple Clique Camouflaging Against Greedy Maximum Clique Heuristics
Stanislav Busygin (busygina-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.
Entry Submitted: 12/19/2002
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|