Artículo
A DSATUR-based algorithm for the Equitable Coloring Problem
Fecha de publicación:
02/2015
Editorial:
Pergamon-Elsevier Science Ltd
Revista:
Computers & Operations Research
ISSN:
0305-0548
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
This paper describes a new exact algorithm for the Equitable Coloring Problem, a coloring problem where the sizes of two arbitrary color classes differ in at most one unit. Based on the well known DSatur algorithm for the classic Coloring Problem, a pruning criterion arising from equity constraints is proposed and analyzed. The good performance of the algorithm is shown through computational experiments over random and benchmark instances.
Palabras clave:
Dsatur
,
Equitable Coloring
,
Exact Algorithm
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - ROSARIO)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Articulos(SEDE CENTRAL)
Articulos de SEDE CENTRAL
Articulos de SEDE CENTRAL
Citación
Méndez-Díaz, Isabel; Nasini, Graciela Leonor; Severin, Daniel Esteban; A DSATUR-based algorithm for the Equitable Coloring Problem; Pergamon-Elsevier Science Ltd; Computers & Operations Research; 57; 2-2015; 41-50
Compartir
Altmétricas