Back to Search
Start Over
A semidefinite programming-based heuristic for graph coloring
- Source :
-
Discrete Applied Mathematics . Jan2008, Vol. 156 Issue 2, p180-189. 10p. - Publication Year :
- 2008
-
Abstract
- Abstract: The Lovász -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. These heuristics could be useful for coloring medium sized graphs as numerical results on DIMACS benchmark graphs indicate. [Copyright &y& Elsevier]
- Subjects :
- *GRAPH coloring
*HEURISTIC programming
*OPERATIONS research
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 156
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 27941161
- Full Text :
- https://doi.org/10.1016/j.dam.2006.07.014