New heuristics for the vertex coloring problem based on semidefinite programming

DOI10.1007/S10100-012-0276-1MaRDI QIDQ351547zbMATH OpenOpenAlexFDO

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

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) Free algebras (08B20) Semialgebraic sets and related spaces (14P10) Real algebra (13J30)

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

Cites work

• A boundary point method to solve semidefinite programs
• A semidefinite programming-based heuristic for graph coloring
• Approximate graph coloring by semidefinite programming
• Block-diagonal semidefinite programming hierarchies for 0/1 programming
• Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
• Copositive and semidefinite relaxations of the quadratic assignment problem
• New approximation guarantee for chromatic number
• On the Shannon capacity of a graph
• Regularization methods for semidefinite programming
• Semidefinite programming relaxations for graph coloring and maximal clique problems

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
• scientific article; zbMATH DE number 6697958 (Why is no real title available?)

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)