Gap, cosum and product properties of the θ′ bound on the clique number
From MaRDI portal
Publication:3066919
DOI10.1080/02331930903395634zbMath1214.05102MaRDI 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; copositive programming; circulant graph; maximum clique problem; graph product
90C22: Semidefinite programming
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C76: Graph operations (line graphs, products, etc.)
Related Items
A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations, A Sum of Squares Characterization of Perfect Graphs, Quadratic factorization heuristics for copositive programming, Factorization and cutting planes for completely positive matrices by copositive projection, Copositivity cuts for improving SDP bounds on the clique number
Cites Work
- 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
- Unnamed Item