A characterization of the weighted Lovász number based on convex quadratic programming

DOI10.1007/s11590-015-0911-6zbMath1360.90225OpenAlexW806449981MaRDI QIDQ5963688

Carlos J. Luz

Publication date: 23 February 2016

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-015-0911-6

zbMATH Keywords

quadratic programmingcombinatorial optimizationgraph theorymaximum weight stable setweighted Lovász number

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27)

Related Items

A survey on graphs with convex quadratic stability number, Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming

Uses Software

• SDPT3
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving semidefinite-quadratic-linear programs using SDPT3
• Relaxations of vertex packing
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization
• A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
• An upper bound on the independence number of a graph computable in polynomial-time
• A review on algorithms for maximum clique problems
• Approximation of the Stability Number of a Graph via Copositive Programming
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• Maxima for Graphs and a New Proof of a Theorem of Turán
• A Convex Quadratic Characterization of the Lovász Theta Number
• A quadratic programming approach to the determination of an upper bound on the weighted stability number
• Finding independent sets in a graph using continuous multivariable polynomial formulations.
• A simplex like approach based on star sets for recognizing convex-\(QP\) adverse graphs