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

DOI10.1007/S10958-009-9613-XMaRDI QIDQ844531zbMATHOpenAlexFDO

Authors Luís 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

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

Recommendations

• A Convex Quadratic Characterization of the Lovász Theta Number
• Improving an upper bound on the stability number of a graph
• A quadratic programming approach to the determination of an upper bound on the weighted stability number
• Applications of the Inverse Theta Number in Stable Set Problems
• An SDP-based approach for computing the stability number of a graph

Cites work

• scientific article; zbMATH DE number 432819 (Why is no real title available?)
• scientific article; zbMATH DE number 46303 (Why is no real title available?)
• scientific article; zbMATH DE number 3573250 (Why is no real title available?)
• A Convex Quadratic Characterization of the Lovász Theta Number
• A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization
• A scatter search algorithm for the maximum clique problem
• An upper bound on the independence number of a graph computable in polynomial-time
• Approximating the independence number via the \(\vartheta\)-function
• Approximation algorithms for combinatorial problems
• Computational Experience with Stable Set Relaxations
• Geometric algorithms and combinatorial optimization
• Maximum stable set formulations and heuristics based on continuous optimization
• 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
• The sandwich theorem
• Two numerical methods for optimizing matrix stability

Cited in

(6)

• Maximum stable set formulations and heuristics based on continuous optimization
• Extended and discretized formulations for the maximum clique problem
• An SDP-based approach for computing the stability number of a graph
• A quadratic programming approach to the determination of an upper bound on the weighted stability number
• A Convex Quadratic Characterization of the Lovász Theta Number
• A survey on graphs with convex quadratic stability number

Describes a project that uses

Uses Software

• GradSamp
• Scatter Search
• Tabu search

This page was built for publication: A heuristic for the stability number of a graph based on convex quadratic programming and tabu search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q844531)