Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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. © 2014 Elsevier Ltd. All rights reserved.

Registro:

Documento: Artículo
Título:A DSATUR-based algorithm for the Equitable Coloring Problem
Autor:Méndez-Díaz, I.; Nasini, G.; Severín, D.
Filiación:Departamento de Ciencias de la Computación, Facultad de Ciencias Exactas y Naturales - FCEyN, Universidad de Buenos Aires, Argentina
FCEIA, Universidad Nacional de Rosario, Argentina
CONICET, Argentina
Palabras clave:DSatur; Equitable coloring; Exact algorithm; Benchmarking; Coloring; Arbitrary color; Coloring problems; Computational experiment; DSatur; Equitable coloring; Exact algorithms; Algorithms
Año:2015
Volumen:57
Página de inicio:41
Página de fin:50
DOI: http://dx.doi.org/10.1016/j.cor.2014.11.014
Título revista:Computers and Operations Research
Título revista abreviado:Comp. Oper. Res.
ISSN:03050548
CODEN:CMORA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03050548_v57_n_p41_MendezDiaz

Referencias:

  • Meyer, W., Equitable coloring (1973) Am Math Mon, 80, pp. 920-922
  • Tucker, A., Perfect graphs and an application to optimizing municipal services (1973) SIAM Rev, 15, pp. 585-590
  • Das, S.K., Finocchi, I., Petreschi, R., Conflict-free star-access in parallel memory systems (2006) J Parallel Distrib Comput, 66, pp. 1431-1441
  • Pemmaraju, S.V., Equitable colorings extend Chernoff-Hoeffding bounds (2001) Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques. Lecture Notes in Computer Science, 2129, pp. 285-296
  • Furmanczyk, H., Kubale, M., Equitable coloring of graphs (2004) Graph Colorings, pp. 35-53. , Providence, Rhode Island: American Mathematical Society
  • Méndez-Díaz, I., Zabala, P., A branch-and-cut algorithm for graph coloring (2006) Discret Appl Math, 154, pp. 826-847
  • Bahiense, L., Frota, Y., Noronha, T.F., Ribeiro, C., A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives (2014) Discret Appl Math, 164, pp. 34-46
  • Campêlo, M., Corrêa, R., Campos, V., On the asymmetric representatives formulation for the vertex coloring problem (2008) Discret Appl Math, 156, pp. 1097-1111
  • Méndez Díaz, I., Nasini, G., Severín, D., A polyhedral approach for the equitable coloring problem (2014) Discret Appl Math, 164, pp. 413-426
  • Brélaz, D., New methods to color the vertices of a graph (1979) Commun ACM, 22, pp. 251-256
  • San-Segundo, P., A new DSATUR-based algorithm for exact vertex coloring (2012) Comput Oper Res, 39, pp. 1724-1733
  • Brown, J.R., Chromatic scheduling and the chromatic number problem (1972) Manag Sci (Part I), 19, pp. 456-463
  • Sewell, E.C., An improved algorithm for exact graph coloring (1996) Proceedings of the Second DIMACS Implementation Challenge, 26, pp. 359-373. , Trick MA, Johnson DS, editors. Cliques, coloring and satisfiability American Mathematical Society
  • Méndez Díaz, I., Nasini, G., Severín, D., An exact DSatur-based algorithm for the equitable coloring problem (2013) Electron Note Discret Math, 44, pp. 281-286
  • Isaacson, J.D., Marble, G., Matula, D.W., Graph coloring algorithms (1972) Graph Theory and Computing, pp. 109-122. , New York: Academic Press
  • Lih, K.-W., Chen, B.-L., Equitable coloring of trees (1994) J Comb Theory, ser B, 61, pp. 83-87
  • Garey, M., Johnson, D., (1979) Computers and Intractability: A Guide to the Theory of NP Completeness, , Freeman San Francisco, CA
  • Hajnal, A., Szemerédi, E., Proof of a conjecture of P. Erdös (1970) Comb Theory Appl, 2, pp. 601-623
  • Kierstead, H.A., Kostochka, A.V., An ore-type theorem on equitable coloring (2008) J Comb Theory ser B, 98, pp. 226-234
  • DIMACS COLORLIB Library, , http://www.mat.gsia.cmu.edu/COLOR03
  • Chen, B.-L., Huang, K.-C., The equitable colorings of Kneser graphs (2008) Taiwan J Math, 12, pp. 887-900
  • Brélaz, D., Nicolier, Y., De Werra, D., Compactness and balancing in scheduling (1977) Math Methods Oper Res, 21, pp. 65-73

Citas:

---------- APA ----------
Méndez-Díaz, I., Nasini, G. & Severín, D. (2015) . A DSATUR-based algorithm for the Equitable Coloring Problem. Computers and Operations Research, 57, 41-50.
http://dx.doi.org/10.1016/j.cor.2014.11.014
---------- CHICAGO ----------
Méndez-Díaz, I., Nasini, G., Severín, D. "A DSATUR-based algorithm for the Equitable Coloring Problem" . Computers and Operations Research 57 (2015) : 41-50.
http://dx.doi.org/10.1016/j.cor.2014.11.014
---------- MLA ----------
Méndez-Díaz, I., Nasini, G., Severín, D. "A DSATUR-based algorithm for the Equitable Coloring Problem" . Computers and Operations Research, vol. 57, 2015, pp. 41-50.
http://dx.doi.org/10.1016/j.cor.2014.11.014
---------- VANCOUVER ----------
Méndez-Díaz, I., Nasini, G., Severín, D. A DSATUR-based algorithm for the Equitable Coloring Problem. Comp. Oper. Res. 2015;57:41-50.
http://dx.doi.org/10.1016/j.cor.2014.11.014