A semidefinite programming-based heuristic for graph coloring

DOI10.1016/j.dam.2006.07.014zbMath1235.05050OpenAlexW2043473394MaRDI QIDQ2467349

Igor Dukanovic, Franz Rendl

Publication date: 21 January 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.07.014

zbMATH Keywords

Lovász theta numberLovász theta functiongraph (vertex) coloring

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Copositive programming motivated bounds on the stability and the chromatic numbers, New heuristics for the vertex coloring problem based on semidefinite programming, Semidefinite programming relaxations for graph coloring and maximal clique problems, A NEW APPROACH TO THE VERTEX COLORING PROBLEM

Uses Software

• SDPLR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using tabu search techniques for graph coloring
• A boundary point method to solve semidefinite programs
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• Semidefinite programming in combinatorial optimization
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Genetic algorithm for graph coloring: exploration of Galinier and Hao's algorithm
• Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
• On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
• Genetic and hybrid algorithms for graph coloring
• Hybrid evolutionary algorithms for graph coloring
• Solving Some Large Scale Semidefinite Programs via the Conjugate Residual Method
• Semidefinite optimization
• Approximate graph coloring by semidefinite programming
• New methods to color the vertices of a graph
• On the Shannon capacity of a graph
• A Column Generation Approach for Graph Coloring
• A Spectral Bundle Method for Semidefinite Programming
• Finding the chromatic number by means of critical graphs
• Chromatic Scheduling and the Chromatic Number Problem