Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903504 | Electronic Notes in Discrete Mathematics | 2017 | 6 Pages |
Abstract
The bandwidth coloring problem (BCP) is a generalization of the well-known vertex coloring problem (VCP), asking colors to be assigned to vertices of a graph such that the absolute difference between the colors assigned to adjacent vertices is greater than or equal to a weight associated to the edge connecting them. In this work we present an integer programming formulation for BCP based on the orientation model for VCP. We present two families of valid inequalities for this formulation, show that they induce facets of the associated polytope, and report computational experience suggesting that these families are useful in practice.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Bruno Dias, Rosiane de Freitas, Nelson Maculan, Javier Marenco,