A semidefinite programming-based heuristic for graph coloring
From MaRDI portal
Publication:2467349
DOI10.1016/j.dam.2006.07.014zbMath1235.05050MaRDI QIDQ2467349
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
90C22: Semidefinite programming
90C27: Combinatorial optimization
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Copositive programming motivated bounds on the stability and the chromatic numbers, Semidefinite programming relaxations for graph coloring and maximal clique problems
Uses Software
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
