Gap, cosum and product properties of the θ′ bound on the clique number

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

zbMATH Keywords

semidefinite programmingcopositive programmingcirculant graphmaximum clique problemgraph product

Mathematics Subject Classification ID

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