A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming
From MaRDI portal
Publication:2788727
DOI10.1142/S1793830915500500zbMath1331.05145MaRDI QIDQ2788727
Publication date: 22 February 2016
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
quadratic programmingcombinatorial optimizationmaximum weight stable setLovász numberMcEliece-Rodemich-Rumsey-Schrijver number
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