Abstract
This paper studies a robust graph coloring problem, which is a variant of the classical graph coloring problem, where penalties are charged for non-adjacent vertices that are assigned the same color. The problem can be formulated as an unconstrained quadratic programming problem, and has many applications in industry. Since the problem is known to be strongly NP-complete, we develop a number of metaheuristics for it, which are based on various encoding schemes, neighborhood structures, and search algorithms. Extensive experiments suggest that our metaheuristics with a partition based encoding scheme and an improvement graph based neighborhood outperform other methods tested in our study.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aardal, K.I., van Hoesel, S.P.M., Koster, A.M.C.A., Mannino, C., Sassano, A.: Models and solution techniques for frequency assignment problems. Ann. Oper. Res. 153(1), 79–129 (2007). ISSN: 0254-5330
Avanthay, C., Hertz, A., Zufferey, N.: A variable neighborhood search for graph coloring. Eur. J. Oper. Res. 151(2), 379–388 (2003)
Blochliger, I., Zufferey, N.: A graph coloring heuristic using partial solutions and a reactive tabu scheme. Comput. Oper. Res. 35(3), 960–975 (2008)
Bracho, R.L., Rodriguez, J.R., Martinez, F.J.Z.: Algorithms for robust graph coloring on paths. In: Proceedings of the 2nd International Conference on Electrical and Electronics Engineering, pp. 9–12 (2005)
Calégari, P., Coray, G., Hertz, A., Kobler, D., Kuonen, P.: A taxonomy of evolutionary algorithms in combinatorial optimization. J. Heuristics 5(2), 145–158 (1999)
Chaitin, G.J.: Register allocation and spilling via graph coloring. In: Proceedings of Symposium on Compiler Construction (ACM SIGPLAN ’82), pp. 98–105 (1982)
Chams, M., Hertz, A., De Werra, D.: Some experiments with simulated annealing for coloring graphs. Eur. J. Oper. Res. 32(2), 260–266 (1987)
Costa, D., Hertz, A., Dubuis, C.: Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs. J. Heuristics 1(1), 105–128 (1995)
Davis, L.: Order-based genetic algorithms and the graph coloring problem. In: Handbook of Genetic Algorithms, pp. 72–90 (1991). Van Nostrand Reinhold Company
Dorne, R., Hao, J.K.: A new genetic local search algorithm for graph coloring. In: Lecture Notes in Computer Science, pp. 745–754. Springer, Berlin (1998)
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, 2547–2562 (2006)
Galinier, P., Hertz, A., Zufferey, N.: An adaptive memory algorithm for the k-coloring problem. Discrete Appl. Math. 156(2), 267–279 (2008)
Gamst, A.: Some lower bounds for a class of frequency assignment problems. IEEE Trans. Veh. Technol. 35(1), 8–14 (1986)
Garey, M.R., Johnson, D.S.: Computer and Intractability: A guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Glover, F., Lu, Z., Hao, J.K.: Diversification-driven tabu search for unconstrained binary quadratic problems. 4OR: Q. J. Oper. Res. 1–15 (2010)
Halldorsson, M.M.: A still better performance guarantee for approximate graph coloring. Inf. Process. Lett. 45(1), 19–23 (1993)
Hertz, A., Werra, D.: Using tabu search techniques for graph coloring. Computing 39(4), 345–351 (1987)
Fleurent, C., Ferland, J.A.: Genetic and hybrid algorithms for graph coloring. Ann. Oper. Res. 63(3), 437–461 (1996). ISSN: 0254-5330
Johnson, D.S., Trick, M.A.: DIMACS Series in Discrete Mathematics and Theoretical Computer Science. In: Proceedings of the 2nd DIMACS Implementation Challenge: Cliques, Coloring, and Satisfiability. vol. 26, pp. 98–105. American Mathematical Society, Providence (1996)
Johnson, D.S., Aragon, C.R., McGeoch, L.A., Schevon, C.: Optimization by simulated annealing: an experimental evaluation. Part II. Graph coloring and number partitioning. Oper. Res. 378–406 (1991)
Kochenberger, G.A., Glover, F., Alidaee, B., Rego, C.: An unconstrained quadratic binary programming approach to the vertex coloring problem. Ann. Oper. Res. 139(1), 229–241 (2005)
Kong, Y., Wang, F., Lim, A., Guo, S.S.: A new hybrid genetic algorithm for the robust graph coloring problem. In: Lecture Notes in Computer Science, pp. 125–136. Springer, Berlin (2003)
Laguna, M., Martí, R.: A GRASP for coloring sparse graphs. Comput. Optim. Appl. 19(2), 165–178 (2001). ISSN: 0926-6003
Malaguti, E., Toth, P.: A survey on vertex coloring problems. Int. Trans. Oper. Res. 17(1), 1–34 (2010) ISSN: 1475-3995
Merz, P., Freisleben, B.: Greedy and local search heuristics for unconstrained binary quadratic programming. J. Heuristics 8(2), 197–213 (2002)
Morgenstern, C.: Distributed coloration neighborhood search. In: Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993, p. 335 (1996)
Opsut, R.J., Roberts, F.S.: On the fleet maintenance, mobile radio frequency, task assignment and traffic phasing problems. In: The Theory and Applications of Graphs, pp. 479–492. Wiley, New York (1981)
Pardalos, P.M., Mavridou, T., Xue, J.: The graph coloring problems: a bibliographic survey. In: Handbook of Combinatorial Optimization, pp. 331–395. Kluwer Academic, Amsterdam (1998)
Yanez, J., Ramirez, J.: The robust coloring problem. Eur. J. Oper. Res. 148(3), 546–558 (2003)
Zufferey, N., Amstutz, P., Giaccari, P.: Graph colouring approaches for a satellite range scheduling problem. J. Sched. 11(4), 263–277 (2008)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, F., Xu, Z. Metaheuristics for robust graph coloring. J Heuristics 19, 529–548 (2013). https://doi.org/10.1007/s10732-011-9180-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-011-9180-4