Navegar

Colección

Datos Estadísticas

Artículo

La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

This paper describes an exact algorithm for the Equitable Coloring Problem, based on the well known DSatur algorithm for the classic Coloring Problem with new pruning rules specifically derived from the equity constraint. Computational experiences show that our algorithm is competitive with those known in literature. © 2013 Elsevier B.V.

Registro:

Documento: Artículo
Título:An exact DSatur-based algorithm for the Equitable Coloring Problem
Autor:Méndez-Díaz, I.; Nasini, G.; Severín, D.
Filiación:FCEyN, Universidad de Buenos Aires, Argentina
FCEIA, Universidad Nacional de Rosario y CONICET Argentina, Argentina
Palabras clave:DSatur; Equitable coloring; Exact algorithm
Año:2013
Volumen:44
Página de inicio:281
Página de fin:286
DOI: http://dx.doi.org/10.1016/j.endm.2013.10.044
Título revista:Electronic Notes in Discrete Mathematics
Título revista abreviado:Electron. Notes Discrete Math.
ISSN:15710653
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v44_n_p281_MendezDiaz

Referencias:

  • Bahiense, L., Frota, Y., Noronha, T.F., Ribeiro, C., A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives Discrete Appl. Math., , In Press
  • Brélaz, D., New methods to color the vertices of a graph (1979) Comm. of the ACM, 22, pp. 251-256
  • Brown, J.R., Chromatic scheduling and the chromatic number problem (1972) Manag. Sci. (Part I), 19, pp. 456-463
  • Furmańczyk, H., Kubale, M., The complexity of equitable vertex coloring of graphs (2005) J. Appl. Comp. Sci., 13, pp. 95-107
  • Lih, K.-W., Chen, B.-L., Equitable coloring of trees (1994) J. Combin. Theory, Series B, 61, pp. 83-87
  • Méndez-Díaz, I., Nasini, G., Severin, D., A polyhedral approach for the Equitable Coloring Problem Discrete Appl. Math., , In Press
  • San Segundo, P., A new DSATUR-based algorithm for exact vertex coloring (2012) Comput. Oper. Res., 39, pp. 1724-1733
  • Sewell, E.C., An improved algorithm for exact graph coloring (1996) DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26, pp. 359-373. , AMS, Providence, Rhode Island

Citas:

---------- APA ----------
Méndez-Díaz, I., Nasini, G. & Severín, D. (2013) . An exact DSatur-based algorithm for the Equitable Coloring Problem. Electronic Notes in Discrete Mathematics, 44, 281-286.
http://dx.doi.org/10.1016/j.endm.2013.10.044
---------- CHICAGO ----------
Méndez-Díaz, I., Nasini, G., Severín, D. "An exact DSatur-based algorithm for the Equitable Coloring Problem" . Electronic Notes in Discrete Mathematics 44 (2013) : 281-286.
http://dx.doi.org/10.1016/j.endm.2013.10.044
---------- MLA ----------
Méndez-Díaz, I., Nasini, G., Severín, D. "An exact DSatur-based algorithm for the Equitable Coloring Problem" . Electronic Notes in Discrete Mathematics, vol. 44, 2013, pp. 281-286.
http://dx.doi.org/10.1016/j.endm.2013.10.044
---------- VANCOUVER ----------
Méndez-Díaz, I., Nasini, G., Severín, D. An exact DSatur-based algorithm for the Equitable Coloring Problem. Electron. Notes Discrete Math. 2013;44:281-286.
http://dx.doi.org/10.1016/j.endm.2013.10.044