Variations on memetic algorithms for graph coloring problems

• Aardal, K., Hoesel, S., Koster, A., Mannino, C., Sassano, A.: Models and solution techniques for frequency assignment problems. Q. J. Belg. Fr. Ital. Oper. Res. Soc. 1(4), 261–317 (2003)

  MathSciNet  MATH  Google Scholar 

• Allignol, C., Barnier, N., Gondran, A.: Optimized flight level allocation at the continental scale. In: International Conference on Research in Air Transportation (ICRAT 2012), Berkeley, California, USA, 22–25 May 2012 (2012)

• Barnier, N., Brisset, P.: Graph coloring for air traffic flow management. Ann. Oper. Res. 130(1–4), 163–178 (2004)

  Article  MathSciNet  MATH  Google Scholar 

• Dib, M., Caminada, A., Mabed, H.: Frequency management in radio military networks. In: INFORMS Telecom 2010, 10th INFORMS Telecommunications Conference Montreal, Canada (2010)

• Dubois, N., de Werra, D.: Epcot: an efficient procedure for coloring optimally with Tabu search. Comput. Math. Appl. 25(10–11), 35–45 (1993)

  Article  MathSciNet  MATH  Google Scholar 

• Fleurent, C., Ferland, J.: Genetic and hybrid algorithms for graph coloring. Ann. Oper. Res. 63, 437–464 (1996)

  Article  MATH  Google Scholar 

• Galinier, P., Hao, J.-K.: Hybrid evolutionary algorithms for graph coloring. J. Comb. Optim. 3(4), 379–397 (1999)

  Article  MathSciNet  MATH  Google Scholar 

• Galinier, P., Hertz, A.: A survey of local search methods for graph coloring. Comput. Oper. Res. 33, 2547–2562 (2006)

  Article  MathSciNet  MATH  Google Scholar 

• Galinier, P., Hertz, A., Zufferey, N.: An adaptive memory algorithm for the \(k\)-coloring problem. Discret. Appl. Math. 156(2), 267–279 (2008)

  Article  MathSciNet  MATH  Google Scholar 

• Galinier, P., Hamiez, J.-P., Hao, J.-K., Porumbel, D.C.: Recent advances in graph vertex coloring. In: Zelinka, I.,  Snásel, V.,  Abraham, A. (eds) Handbook of Optimization, Vol. 38 of Intelligent Systems Reference Library, pp. 505–528. Springer, Berlin (2013)

• Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of \({\cal{NP}}\)-Completeness. Freeman, San Francisco (1979)

  MATH  Google Scholar 

• Gusfield, D.: Partition-distance: a problem and class of perfect graphs arising in clustering. Inf. Process. Lett. 82(3), 159–164 (2002)

  Article  MathSciNet  MATH  Google Scholar 

• Hao, J.-K.: Memetic algorithms in discrete optimization. In: Neri, F.,  Cotta, C.,  Moscato, P. (eds.) Handbook of Memetic Algorithms, Vol. 379 of Studies in Computational Intelligence, pp. 73–94. Springer, Berlin (2012)

• Hao, J.-K., Wu, Q.: Improving the extraction and expansion method for large graph coloring. Discret. Appl. Math. 160(16–17), 2397–2407 (2012)

  Article  MathSciNet  MATH  Google Scholar 

• Held, S., Cook, W., Sewell, E.C.: Safe lower bounds for graph coloring. In: Günlük, O., Woeginger, G.J. (eds.) Integer Programming and Combinatoral Optimization. IPCO 2011. Lecture Notes in Computer Science, Vol. 6655. Springer, Berlin, Heidelberg (2011)

• Hertz, A., de Werra, D.: Using Tabu search techniques for graph coloring. Computing 39(4), 345–351 (1987)

  Article  MathSciNet  MATH  Google Scholar 

• Hertz, A., Plumettaz, M., Zufferey, N.: Variable space search for graph coloring. Discret. Appl. Math. 156(13), 2551–2560 (2008)

  Article  MathSciNet  MATH  Google Scholar 

• Johnson, D.S., Trick, M.: Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993, Vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 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. 39(3), 378–406 (1991)

  Article  MATH  Google Scholar 

• Karp, R.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)

  Chapter  Google Scholar 

• Leighton, F.T.: A graph coloring algorithm for large scheduling problems. J. Res. Natl. Bur. Stand. 84(6), 489–506 (1979)

  Article  MathSciNet  MATH  Google Scholar 

• Lewis, R.: Graph coloring and recombination. In: Kacprzyk, J., Pedrycz, W. (eds.) Handbook of Computational Intelligence, pp. 1239–1254. Springer, Berlin (2015). (Ch. Graph Coloring and Recombination)

• Lü, Z., Hao, J.-K.: A memetic algorithm for graph coloring. Eur. J. Oper. Res. 203(1), 241–250 (2010)

  Article  MathSciNet  MATH  Google Scholar 

• Malaguti, E., Toth, P.: A survey on vertex coloring problems. Int. Trans. Oper. Res. 17(1), 1–34 (2010)

  Article  MathSciNet  MATH  Google Scholar 

• Malaguti, E., Monaci, M., Toth, P.: An exact approach for the vertex coloring problem. Discret. Optim. 8(2), 174–190 (2011)

  Article  MathSciNet  MATH  Google Scholar 

• Porumbel, D.C., Hao, J.-K., Kuntz, P.: An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Comput. Oper. Res. 37, 1822–1832 (2010)

  Article  MATH  Google Scholar 

• Titiloye, O., Crispin, A.: Graph coloring with a distributed hybrid quantum annealing algorithm. In: O’Shea, J., Nguyen, N., Crockett, K., Howlett, R., Jain, L. (eds.) Agent and Multi-Agent Systems: Technologies and Applications. Lecture Notes in Computer Science, vol. 6682, pp. 553–562. Springer, Berlin (2011a)

  Chapter  Google Scholar 

• Titiloye, O., Crispin, A.: Quantum annealing of the graph coloring problem. Discret. Optim. 8(2), 376–384 (2011b)

  Article  MathSciNet  MATH  Google Scholar 

• Titiloye, O., Crispin, A.: Parameter tuning patterns for random graph coloring with quantum annealing. PLoS ONE 7(11), e50060 (2012)

  Article  Google Scholar 

• Wood, D.C.: A technique for coloring a graph applicable to large-scale timetabling problems. Comput. J. 12, 317–322 (1969)

  Article  MathSciNet  MATH  Google Scholar 

• Wu, Q., Hao, J.-K.: Coloring large graphs based on independent set extraction. Comput. Oper. Res. 39(2), 283–290 (2012)

  Article  MathSciNet  MATH  Google Scholar 

• Zufferey, N., Amstutz, P., Giaccari, P.: Graph colouring approaches for a satellite range scheduling problem. J. Sched. 11(4), 263–277 (2008)

  Article  MathSciNet  MATH  Google Scholar 

Download references