New heuristics for the vertex coloring problem based on semidefinite programming
DOI10.1007/S10100-012-0276-1zbMATH Open1267.90094OpenAlexW2032367325MaRDI QIDQ351547FDOQ351547
Authors: Jelena Govorčin, Nebojša Gvozdenović, Janez Povh 
Publication date: 8 July 2013
Published in: CEJOR. Central European Journal of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10100-012-0276-1
Recommendations
- A semidefinite programming-based heuristic for graph coloring
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Approximate graph coloring by semidefinite programming
- A lower bound for the chromatic number of a graph
- Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
Semidefinite programming (90C22) Linear operator methods in interpolation, moment and extension problems (47A57) Free algebras (08B20) Semialgebraic sets and related spaces (14P10) Real algebra (13J30)
Cites Work
- Regularization methods for semidefinite programming
- Approximate graph coloring by semidefinite programming
- On the Shannon capacity of a graph
- Copositive and semidefinite relaxations of the quadratic assignment problem
- A boundary point method to solve semidefinite programs
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Block-diagonal semidefinite programming hierarchies for 0/1 programming
- A semidefinite programming-based heuristic for graph coloring
- New approximation guarantee for chromatic number
- Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
Cited In (9)
- A semidefinite programming-based heuristic for graph coloring
- \(L(3,2,1)\)-labeling of triangular and toroidal grids
- Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Models and heuristic algorithms for a weighted vertex coloring problem
- Methodologies and applications for resilient global development from the aspect of SDI-SOR special issues of CJOR
- Collective dynamics of phase-repulsive oscillators solves graph coloring problem
- New variable neighborhood search method for minimum sum coloring problem on simple graphs
- Title not available (Why is that?)
This page was built for publication: New heuristics for the vertex coloring problem based on semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q351547)
