Gap, cosum and product properties of the θ′ bound on the clique number
From MaRDI portal
Publication:3066919
DOI10.1080/02331930903395634zbMath1214.05102OpenAlexW2045652008MaRDI QIDQ3066919
Florian Frommlet, Immanuel M. Bomze, Marco Locatelli
Publication date: 20 January 2011
Published in: Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/02331930903395634
Semidefinite programming (90C22) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)
Related Items
Copositivity cuts for improving SDP bounds on the clique number, A Sum of Squares Characterization of Perfect Graphs, Factorization and cutting planes for completely positive matrices by copositive projection, Quadratic factorization heuristics for copositive programming, A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations
Cites Work
- Unnamed Item
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability
- Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
- Approximation of the Stability Number of a Graph via Copositive Programming
- A comparison of the Delsarte and Lovász bounds
- On the Shannon capacity of a graph
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming