New heuristics for the vertex coloring problem based on semidefinite programming

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

Central European Journal of Operations Research, 2013, vol. 21, issue 1, 13-25

Abstract: The Lovász theta number Lovász (IEEE Trans Inf Theory 25:1–7, 1979 ) is a well-known lower bound on the chromatic number of a graph $$G$$ , and $$\varPsi _K(G)$$ is its impressive strengthening Gvozdenović and Laurent (SIAM J Optim 19(2):592–615, 2008 ). The bound $$\varPsi _K(G)$$ was introduced in very specific and abstract setting which is tough to translate into usual mathematical programming framework. In the first part of this paper we unify the motivations and approaches to both bounds and rewrite them in a very similar settings which are easy to understand and straightforward to implement. In the second part of the paper we provide explanations how to solve efficiently the resulting semidefinite programs and how to use optimal solutions to get good coloring heuristics. We propose two vertex coloring heuristics based on $$\varPsi _K(G)$$ and present numerical results on medium sized graphs. Copyright Springer-Verlag Berlin Heidelberg 2013

Keywords: Semidefinite programming; Vertex coloring problem; Boundary point method; 90C22; 13J30; 14P10; 47A57; 08B20 (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10100-012-0276-1 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:cejnor:v:21:y:2013:i:1:p:13-25

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10100

DOI: 10.1007/s10100-012-0276-1

Access Statistics for this article

Central European Journal of Operations Research is currently edited by Ulrike Leopold-Wildburger

More articles in Central European Journal of Operations Research from Springer, Slovak Society for Operations Research, Hungarian Operational Research Society, Czech Society for Operations Research, Österr. Gesellschaft für Operations Research (ÖGOR), Slovenian Society Informatika - Section for Operational Research, Croatian Operational Research Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().