Simple ingredients leading to very efficient heuristics for the maximum clique problem

DOI10.1007/s10732-007-9055-xzbMath1173.90565OpenAlexW1994203526MaRDI QIDQ1009196

Andrea Grosso, Marco Locatelli, Wayne Pullan

Publication date: 31 March 2009

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10732-007-9055-x

zbMATH Keywords

randomnessmaximum cliquepenaltiesplateau searchrestart rules

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Subgraph extraction and metaheuristics for the maximum clique problem ⋮ Phased local search for the maximum clique problem ⋮ A review on algorithms for maximum clique problems ⋮ On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem ⋮ Extended and discretized formulations for the maximum clique problem ⋮ An adaptive multistart tabu search approach to solve the maximum clique problem ⋮ Finding near-optimal independent sets at scale ⋮ Solving the maximum clique problem with symmetric rank-one non-negative matrix approximation ⋮ A Wide Branching Strategy for the Graph Coloring Problem ⋮ Minimum energy target tracking with coverage guarantee in wireless sensor networks ⋮ An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem† ⋮ SQBC: an efficient subgraph matching method over large and dense graphs ⋮ An exact approach for the vertex coloring problem ⋮ Local search with edge weighting and configuration checking heuristics for minimum vertex cover ⋮ A simple and effective algorithm for the MaxMin diversity problem ⋮ Improvements to MCS algorithm for the maximum clique problem ⋮ Incremental Upper Bound for the Maximum Clique Problem ⋮ Fast local search for the maximum independent set problem ⋮ PUSH: A generalized operator for the maximum vertex weight clique problem ⋮ Speeding up branch and bound algorithms for solving the maximum clique problem ⋮ Cliques with maximum/minimum edge neighborhood and neighborhood density ⋮ Conflict resolving -- a local search algorithm for solving large scale conflict graphs in freight railway timetabling ⋮ Construction and improvement algorithms for dispersion problems ⋮ Maximum cut-clique problem: ILS heuristics and a data analysis application ⋮ A heuristic approach for the max-min diversity problem based on max-clique ⋮ Speeding up MCS Algorithm for the Maximum Clique Problem with ILS Heuristic and Other Enhancements ⋮ An analysis of parameter adaptation in reactive tabu search

Uses Software

• QUALEX
• Max-AO
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Variable neighborhood search for the maximum clique
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• An effective local search for the maximum clique problem
• An algorithm for finding a maximum clique in a graph
• Maximum stable set formulations and heuristics based on continuous optimization
• A fast algorithm for the maximum clique problem
• Competition polysemy
• A new trust region technique for the maximum weight clique problem
• A hybrid heuristic for the maximum clique problem
• A study of ACO capabilities for solving the maximum clique problem
• Global Optimization with Polynomials and the Problem of Moments
• Approximation of the Stability Number of a Graph via Copositive Programming
• A Complementary Pivoting Approach to the Maximum Weight Clique Problem
• Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials
• A comparison of the Delsarte and Lovász bounds
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem
• Reactive local search for the maximum clique problem
• Adaptive, restart, randomized greedy heuristics for maximum clique