Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
From MaRDI portal
Publication:877197
DOI10.1007/S10107-006-0062-8zbMATH Open1113.90117OpenAlexW4246855957MaRDI QIDQ877197FDOQ877197
Authors: Nebojša Gvozdenović, Monique Laurent 
Publication date: 19 April 2007
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-006-0062-8
Recommendations
- Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
- Finite convergence of sum-of-squares hierarchies for the stability number of a graph
- Lower bounds on the stability number of graphs computed in terms of degrees
- Approximation of the stability number of a graph via copositive programming
- A survey on graphs with convex quadratic stability number
- Certificates for properties of stability polynomials of graphs
- On the stability of common neighbor polynomial of some graphs
- Graphs with least eigenvalue \(-2\) attaining a convex quadratic upper bound for the stability number
- Bounds on the stability number of a graph via the inverse theta function
Cites Work
- Semidefinite Programming
- Geometric algorithms and combinatorial optimization
- Global optimization with polynomials and the problem of moments
- On the Shannon capacity of a graph
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Approximation of the stability number of a graph via copositive programming
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Title not available (Why is that?)
- Optimization of Polynomials on Compact Semialgebraic Sets
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
- LMI Approximations for Cones of Positive Semidefinite Forms
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Title not available (Why is that?)
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Sums of even powers of real linear forms
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
- New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
- A comparison of the Delsarte and Lovász bounds
- Strengthened semidefinite programming bounds for codes
- A new trust region technique for the maximum weight clique problem
- Title not available (Why is that?)
- Semidefinite programming and integer programming
- Title not available (Why is that?)
Cited In (17)
- Sum of squares basis pursuit with linear and second order cone programming
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
- Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
- Handelman's hierarchy for the maximum stable set problem
- Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph
- Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems
- Computing the distance between the linear matrix pencil and the completely positive cone
- Independent sets in graphs
- A new branch-and-bound algorithm for standard quadratic programming problems
- Sum-of-squares certificates for copositivity via test states
- A note on the Lasserre hierarchy for different formulations of the maximum independent set problem
- On the exactness of sum-of-squares approximations for the cone of \(5 \times 5\) copositive matrices
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
- Mathematical Programming Models and Exact Algorithms
- A comprehensive analysis of polyhedral lift-and-project methods
- Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials
- Approximation hierarchies for copositive cone over symmetric cone and their comparison
Uses Software
This page was built for publication: Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q877197)
