Semidefinite programming relaxations for graph coloring and maximal clique problems

DOI10.1007/s10107-006-0026-zzbMath1278.90299MaRDI QIDQ868457

Franz Rendl, Igor Dukanovic

Publication date: 5 March 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-0026-z

zbMATH Keywords

chromatic number; clique number; cutting planes; Lovász theta number

Mathematics Subject Classification ID

90C22: Semidefinite programming

05C25: Graphs and abstract algebra (groups, rings, fields, etc.)

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

A boundary point method to solve semidefinite programs, Simple ingredients leading to very efficient heuristics for the maximum clique problem, A simple simulated annealing algorithm for the maximum clique problem, A semidefinite programming-based heuristic for graph coloring, Binary Positive Semidefinite Matrices and Associated Integer Polytopes

Uses Software

• SDPLR
• COL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using tabu search techniques for graph coloring
• Copositive programming motivated bounds on the stability and the chromatic numbers
• A boundary point method to solve semidefinite programs
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• Geometric algorithms and combinatorial optimization
• The sandwich theorem
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Improved lower bound on the Shannon capacity of \(C_7\)
• Symmetry groups, semidefinite programs, and sums of squares
• On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
• A semidefinite programming-based heuristic for graph coloring
• Solving Some Large Scale Semidefinite Programs via the Conjugate Residual Method
• New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
• Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials
• Some NP-complete problems in quadratic and nonlinear programming
• Approximate graph coloring by semidefinite programming
• A comparison of the Delsarte and Lovász bounds
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• Computational Experience with Stable Set Relaxations
• A Spectral Bundle Method for Semidefinite Programming
• Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
• Solving Lift-and-Project Relaxations of Binary Integer Programs