Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials
From MaRDI portal
Publication:3596364
DOI10.1007/11496915_11zbMath1119.05323OpenAlexW1995151594MaRDI QIDQ3596364
Nebojša Gvozdenović, Monique Laurent
Publication date: 30 August 2007
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11496915_11
Semidefinite programming (90C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Copositive programming motivated bounds on the stability and the chromatic numbers, Copositivity cuts for improving SDP bounds on the clique number, Semidefinite programming relaxations for graph coloring and maximal clique problems, Exploiting equalities in polynomial programming, Copositive Programming, Simple ingredients leading to very efficient heuristics for the maximum clique problem, Completely positive reformulations for polynomial optimization
