A heuristic for the stability number of a graph based on convex quadratic programming and tabu search

DOI10.1007/s10958-009-9613-xzbMath1216.05099OpenAlexW2157797797MaRDI QIDQ844531

L. Cavique, Carlos J. Luz

Publication date: 19 January 2010

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10400.2/1901

Mathematics Subject Classification ID

Convex programming (90C25) Quadratic programming (90C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Extended and discretized formulations for the maximum clique problem ⋮ A survey on graphs with convex quadratic stability number

Uses Software

• GradSamp
• Scatter Search
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric algorithms and combinatorial optimization
• Approximation algorithms for combinatorial problems
• The sandwich theorem
• Approximating the independence number via the \(\vartheta\)-function
• Maximum stable set formulations and heuristics based on continuous optimization
• Two numerical methods for optimizing matrix stability
• An upper bound on the independence number of a graph computable in polynomial-time
• Methods of descent for nondifferentiable optimization
• On extracting maximum stable sets in perfect graphs using Lovász's theta function
• On the Shannon capacity of a graph
• Computational Experience with Stable Set Relaxations
• A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization
• A Convex Quadratic Characterization of the Lovász Theta Number