Abstract
The Equitable Coloring Problem is a variant of the Graph Coloring Problem where the sizes of two arbitrary color classes differ in at most one unit. This additional condition, called equity constraints, arises naturally in several applications. Due to the hardness of the problem, current exact algorithms can not solve large-sized instances. Such instances must be addressed only via heuristic methods.
In this paper we present a tabu search heuristic for the Equitable Coloring Problem. This algorithm is an adaptation of the dynamic TabuCol version of Galinier and Hao. In order to satisfy equity constraints, new local search criteria are given.
Computational experiments are carried out in order to find the best combination of parameters involved in the dynamic tenure of the heuristic. Finally, we show the good performance of our heuristic over known benchmark instances.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Meyer, W.: Equitable coloring. Amer. Math. Mon. 80, 920–922 (1973)
Tucker, A.: Perfect graphs and an application to optimizing municipal services. SIAM Rev. 15, 585–590 (1973)
Das, S.K., Finocchi, I., Petreschi, R.: Conflict-free star-access in parallel memory systems. J. Parallel Distrib. Comput. 66, 1431–1441 (2006)
Pemmaraju, S.V.: Equitable coloring extends Chernoff-Hoeffding bounds. In: Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX-RANDOM 2001. LNCS, vol. 2129, p. 285. Springer, Heidelberg (2001)
Furmanczyk, H., Kubale, M.: Equitable coloring of graphs. In: Kubale, M. (ed.) Graph Colorings, pp. 35–53. American Mathematical Society, Providence (2004)
Hajnal, A., Szemerédi, E.: Proof of a conjecture of P. Erdös. Combin. theory and its app. 2, 601–623 (1970)
Kierstead, H., Kostochka, A., Mydlarz, M., Szemerédi, E.: A fast algorithm for equitable coloring. Combinatorica 30, 217–224 (2010)
Brélaz, D., Nicolier, Y., de Werra, D.: Compactness and balancing in scheduling. Math. Methods Oper. Res. 21, 65–73 (1977)
Sulong, G.B.: Some balanced colouring algorithms for examination timetabling. Jurnal Teknologi 19, 57–63 (1992)
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. 164(1), 34–46 (2014)
Méndez Díaz, I., Nasini, G., Severín, D.: A polyhedral approach for the equitable coloring problem. Discrete Appl. Math. 164(2), 413–426 (2014)
Méndez Díaz, I., Nasini, G., Severín, D.: An exact DSatur-based algorithm for the equitable coloring problem. Electron. Notes Discrete Math. 44, 281–286 (2013)
Galinier, P., Hao, J.-K.: Hybrid evolutionary algorithms for graph coloring. J. Comb. Optim. 3(4), 379–397 (1999)
Galinier, P., Hertz, A.: A survey of local search methods for graph coloring. Comput. Oper. Res. 33(9), 2547–2562 (2006)
Glover, F., McMillan, C., Novick, B.: Interactive decision software and computer graphics for architectural and space planning. Ann. Oper. Res. 5(3), 557–573 (1985)
Hertz, A., de Werra, D.: Using tabu search techniques for graph coloring. Computing 39(4), 345–351 (1987)
Blöchliger, I., Zufferey, N.: A graph coloring heuristic using partial solutions and a reactive tabu scheme. Comput. Oper. Res. 35(3), 960–975 (2008)
Graph Coloring Benchmark Instances. http://www.cs.hbg.psu.edu/txn131/graphcoloring.html
Acknowledgements
This work is partially supported by grants UBACYT 20020100100666, PICT 2010-304, PICT 2011-817, PID-UNR ING416 and PIP-CONICET 241.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Méndez Díaz, I., Nasini, G., Severín, D. (2014). A Tabu Search Heuristic for the Equitable Coloring Problem. In: Fouilhoux, P., Gouveia, L., Mahjoub, A., Paschos, V. (eds) Combinatorial Optimization. ISCO 2014. Lecture Notes in Computer Science(), vol 8596. Springer, Cham. https://doi.org/10.1007/978-3-319-09174-7_30
Download citation
DOI: https://doi.org/10.1007/978-3-319-09174-7_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09173-0
Online ISBN: 978-3-319-09174-7
eBook Packages: Computer ScienceComputer Science (R0)