A semidefinite programming based heuristic for graph coloring
Igor Dukanovic (igor.matuni-mb.si)
Abstract: The Lovasz theta function is a well-known polynomial lower bound on the chromatic number. . Any near optimal solution of its semidefinite programming formulation carries valuable information on how to color the graph. A self-contained presentation of the role of this formulation in obtaining heuristics for the graph coloring problem is presented.
Keywords: Graph (vertex) coloring, Lovasz theta number
Category 1: Combinatorial Optimization (Graphs and Matroids )
Citation: Submitted to Discrete Applied Mathematics, Special Issue on Computational Methods in Graph Coloring.
Entry Submitted: 04/20/2005
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|