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