Artículo

Polyhedral results for the equitable coloring problem

Méndez Díaz, Isabel; Nasini, Graciela LeonorIcon ; Severin, Daniel EstebanIcon
Fecha de publicación: 08/2011
Editorial: Elsevier
Revista: Electronic Notes in Discrete Mathematics
ISSN: 1571-0653
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

Resumen

In this work we study the polytope associated with a 0/1 integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence of the effectiveness of including these inequalities as cuts in a Branch & Cut algorithm.
Palabras clave: BRANCH & CUT , EQUITABLE GRAPH COLORING , INTEGER PROGRAMMING
 
Archivos asociados
Thumbnail
 
Tamaño: 180.0Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Atribución-NoComercial-SinDerivadas 2.5 Argentina (CC BY-NC-ND 2.5 AR)
Identificadores
URI: http://hdl.handle.net/11336/191962
DOI: http://dx.doi.org/10.1016/j.endm.2011.05.028
URL: https://www.sciencedirect.com/science/article/pii/S1571065311000291
Colecciones
Articulos(SEDE CENTRAL)
Articulos de SEDE CENTRAL
Citación
Méndez Díaz, Isabel; Nasini, Graciela Leonor; Severin, Daniel Esteban; Polyhedral results for the equitable coloring problem; Elsevier; Electronic Notes in Discrete Mathematics; 37; 8-2011; 159-164
Compartir
Altmétricas