New heuristics for the vertex coloring problem based on semidefinite programming

DOI10.1007/s10100-012-0276-1zbMath1267.90094OpenAlexW2032367325MaRDI QIDQ351547

Jelena Govorčin, Janez Povh, Nebojša Gvozdenović

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

zbMATH Keywords

semidefinite programmingboundary point methodvertex coloring problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Linear operator methods in interpolation, moment and extension problems (47A57) Semialgebraic sets and related spaces (14P10) Free algebras (08B20) Real algebra (13J30)

Related Items (3)

\(L(3,2,1)\)-labeling of triangular and toroidal grids ⋮ Collective dynamics of phase-repulsive oscillators solves graph coloring problem ⋮ Methodologies and applications for resilient global development from the aspect of SDI-SOR special issues of CJOR

Cites Work

• 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
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• Regularization Methods for Semidefinite Programming

This page was built for publication: New heuristics for the vertex coloring problem based on semidefinite programming