A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming

DOI10.1142/S1793830915500500zbMath1331.05145MaRDI QIDQ2788727

Carlos J. Luz

Publication date: 22 February 2016

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

zbMATH Keywords

quadratic programmingcombinatorial optimizationmaximum weight stable setLovász numberMcEliece-Rodemich-Rumsey-Schrijver number

Mathematics Subject Classification ID

Convex programming (90C25) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Relaxations of vertex packing
• 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
• A comparison of the Delsarte and Lovász bounds
• Cones of Matrices and Set-Functions and 0–1 Optimization
• 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