Annealed replication: A new heuristic for the maximum clique problem

DOI10.1016/S0166-218X(01)00233-5zbMath1019.90032OpenAlexW2119025565MaRDI QIDQ1613385

Marcello Pelillo, Immanuel M. Bomze, Marco Budinich, Claudio Rossi

Publication date: 29 August 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00233-5

zbMATH Keywords

dynamical systemscombinatorial optimizationreplicator dynamicsstable setquadratic optimizationindependent set

Mathematics Subject Classification ID

Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Exact and approximate algorithms for movement problems on (special classes of) graphs, Breakout local search for maximum clique problems, A General Regularized Continuous Formulation for the Maximum Clique Problem, An improved algorithm to test copositivity, Image labeling by assignment, A simple simulated annealing algorithm for the maximum clique problem, Metastability in stochastic replicator dynamics, Approximating the maximum vertex/edge weighted clique using local search, An effective local search for the maximum clique problem, Solving maximum independent set by asynchronous distributed hopfield-type neural networks

Uses Software

• DIMACS

Cites Work

• Optimization by Simulated Annealing
• Lotka-Volterra equation and replicator dynamics: A two-dimensional classification
• The dynamics of nonlinear relaxation labeling processes.
• Non-cooperative two-person games in biology: A classification
• Evolutionarily stable strategies and game dynamics
• Evolution towards the maximum clique
• Genetic engineering via negative fitness: Evolutionary dynamics for global optimization
• Exact bounds on the order of the maximum clique of a graph.
• Lotka-Volterra equation and replicator dynamics: New issues in classification
• Growth transformations for functions on manifolds
• Stability of the center-stable manifold
• The stable, center-stable, center, center-unstable, unstable manifolds
• Mathematical models, problems, and controversies of evolutionary theory
• A global optimization approach for solving the maximum clique problem
• Continuous Characterizations of the Maximum Clique Problem
• Interactive proofs and the hardness of approximating cliques
• An Introduction to the Application of the Theory of Probabilistic Functions of a Markov Process to Automatic Speech Recognition
• Efficient probabilistically checkable proofs and applications to approximations
• Maxima for Graphs and a New Proof of a Theorem of Turán
• An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item