Back to Search
Start Over
Facet-inducing inequalities and a cut-and-branch for the bandwidth coloring polytope based on the orientation model.
- Source :
- Electronic Notes in Discrete Mathematics; Nov2017, Vol. 62, p141-146, 6p
- Publication Year :
- 2017
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 15710653
- Volume :
- 62
- Database :
- Supplemental Index
- Journal :
- Electronic Notes in Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 125922153
- Full Text :
- https://doi.org/10.1016/j.endm.2017.10.025