An unconstrained quadratic binary programming approach to the vertex coloring problem

An unconstrained quadratic binary programming approach to the vertex coloring problem

0.00 Avg rating0 Votes
Article ID: iaor20061016
Country: Netherlands
Volume: 139
Issue: 1
Start Page Number: 229
End Page Number: 241
Publication Date: Oct 2005
Journal: Annals of Operations Research
Authors: , , ,
Keywords: graphs, heuristics
Abstract:

The vertex coloring problem has been the subject of extensive research for many years. Driven by application potential as well as computational challenge, a variety of methods have been proposed for this difficult class of problems. Recent successes in the use of the unconstrained quadratic programming (UQP) model as a unified framework for modeling and solving combinatorial optimization problems have motivated a new approach to the vertex coloring problem. In this paper we present a UQP approach to this problem and illustrate its attractiveness with preliminary computational experience.

Reviews

Required fields are marked *. Your email address will not be published.