Artículo

A polyhedral approach for the equitable coloring problem

Méndez-Díaz, Isabel; Nasini, Graciela LeonorIcon ; Severin, Daniel EstebanIcon
Fecha de publicación: 02/2014
Editorial: Elsevier Science
Revista: Discrete Applied Mathematics
ISSN: 0166-218X
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 that shows the efficacy of these inequalities used in a cutting-plane algorithm.
Palabras clave: CUT AND BRANCH , EQUITABLE GRAPH COLORING , INTEGER PROGRAMMING
 
Archivos asociados
Thumbnail
 
Tamaño: 383.4Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Unported (CC BY-NC-SA 2.5)
Identificadores
URI: http://hdl.handle.net/11336/85989
DOI: http://dx.doi.org/10.1016/j.dam.2012.11.018
URL: https://www.sciencedirect.com/science/article/pii/S0166218X12004477
Colecciones
Articulos(CCT - ROSARIO)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Articulos(SEDE CENTRAL)
Articulos de SEDE CENTRAL
Citación
Méndez-Díaz, Isabel; Nasini, Graciela Leonor; Severin, Daniel Esteban; A polyhedral approach for the equitable coloring problem; Elsevier Science; Discrete Applied Mathematics; 164; Part 2; 2-2014; 413-426
Compartir
Altmétricas