On transitions in the behaviour of tabu search algorithm TabuCol for graph colouring

References

• Aleliunas, R., Karp, R. M., Lipton, R. J., Lovasz, L., & Rackoff, C. (1979). Random walks, universal traversal sequences, and the complexity of maze problems. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science, FOCS ’79 (pp. 218–223), New York, NY.
   Google Scholar
• Auger, A., & Doerr, B. (Eds.). (2011). Theory of randomized search heuristics (Vol. 1). Singapore: World Scientific.
   Google Scholar
• Blöchliger, I., & Zufferey, N. (2008). A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers & Operations Research, 35, 960–975.
   Web of Science ®Google Scholar
• Burke, E. K., McCollum, B., Meisels, A., Petrovic, S., & Qu, R. (2007). A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research, 176, 177–192.
   Web of Science ®Google Scholar
• Chalupa, D. (2011). Population-based and learning-based metaheuristic algorithms for the graph coloring problem. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (pp. 465–472), New York, NY.
   Google Scholar
• Chalupa, D. (2017). An analysis of a simple local search algorithm for graph colouring. ArXiv e-prints, arXiv:1703.05129.
   Google Scholar
• Dorne, R., & Hao, J.-K. (1998). A new genetic local search algorithm for graph coloring. In A. E. Eiben, T. Bäck, M. Schoenauer, & H.-P. Schwefel (Eds.), Proceedings of the 5th International Conference on Parallel Problem Solving from Nature: PPSN ’98 (Vol. 1498, pp. 745–754). Berlin: Springer.
   Google Scholar
• Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., & Witt, C. (2009). Analyses of simple hybrid algorithms for the vertex cover problem. Evolutionary Computation, 17, 3–19.
   PubMed Web of Science ®Google Scholar
• Galinier, P., Hamiez, J.-P., Hao, J.-K., & Porumbel, D. (2013). Recent advances in graph vertex coloring. In Zelinka, I., Sn{\’a}{\v{s}}el, V., & Abraham, A. (Eds.), Handbook of optimization (pp. 505–528). Berlin: Springer.
   Google Scholar
• Galinier, P., & Hao, J. K. (1999). Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization, 3, 379–397.
   Web of Science ®Google Scholar
• Galinier, P., & Hertz, A. (2006). A survey of local search methods for graph coloring. Computers & Operations Research, 33, 2547–2562.
   Web of Science ®Google Scholar
• Giaro, K., Kubale, M., & Obszarski, P. (2009). A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints. Discrete Applied Mathematics, 157, 3625–3630.
   Web of Science ®Google Scholar
• Glass, C. A., & Prügel-Bennett, A. (2003). Genetic algorithm for graph coloring: Exploration of Galinier and Hao’s algorithm. Journal of Combinatorial Optimization, 7, 229–236.
   Web of Science ®Google Scholar
• Glover, F. (1989). Tabu search -- Part I. INFORMS Journal on Computing, 1, 190–206.
   Google Scholar
• Glover, F. (1990). Tabu search -- Part II. INFORMS Journal on Computing, 2, 4–32.
   Google Scholar
• Glover, F., & Laguna, M. (2013). Tabu search. In P. M. Pardalos, D. Z. Du, & R. L. Graham (Eds.), Handbook of combinatorial optimization (pp. 3261–3362). New York, NY: Springer.
   Google Scholar
• Gualandi, S., & Malucelli, F. (2012). Exact solution of graph coloring problems via constraint programming and column generation. INFORMS Journal on Computing, 24, 81–100.
   Web of Science ®Google Scholar
• Hao, J. K., & Wu, Q. (2012). Improving the extraction and expansion method for large graph coloring. Discrete Applied Mathematics, 160, 2397–2407.
   Web of Science ®Google Scholar
• Hawick, K. A., & James, H. A. (2006). Ising model scaling behaviour on z-preserving small-world networks. arXiv preprint cond-mat/0611763.
   Google Scholar
• Held, S., Cook, W., & Sewell, E. (2012). Maximum-weight stable sets and safe lower bounds for graph coloring. Mathematical Programming Computation, 4, 363–381.
   Google Scholar
• Hertz, A., & de Werra, D. (1987). Using tabu search techniques for graph coloring. Computing, 39, 345–351.
   Web of Science ®Google Scholar
• Hertz, A., Plumettaz, M., & Zufferey, N. (2008). Variable space search for graph coloring. Discrete Applied Mathematics, 156, 2551–2560.
   Web of Science ®Google Scholar
• Hoos, H. H., & Stützle, T. (2004). Stochastic local search: Foundations & applications. Amsterdam: Elsevier.
   Google Scholar
• Johnson, D. S. (1974). Worst case behavior of graph coloring algorithms. In F. Hoffman (Ed.), Proceedings of the 5th Southeast Conference on Combinatorics, Graph Theory, and Computing (pp. 513–527). Boca Raton, FL: Florida Atlantic University.
   Google Scholar
• Johnson, D. S., & Trick, M. (1996). Cliques, coloring, and satisfiability: Second DIMACS implementation challenge. Providence, RI: American Mathematical Society.
   Google Scholar
• Karp, R. M. (1972). Reducibility among combinatorial problems. In R. Miller & J. Thatcher (Eds.), Proceedings of a Symposium on the Complexity of Computer Computations (pp. 85–103). New York, NY: Plenum Press.
   Google Scholar
• Kratsch, S., & Neumann, F. (2013). Fixed-parameter evolutionary algorithms and the vertex cover problem. Algorithmica, 65, 754–771.
   Web of Science ®Google Scholar
• Lehre, P. K. (2011). Fitness-levels for non-elitist populations. In N. Krasnogor & P. L. Lanzi (Eds.), Proceedings of the 13th Annual Conference Genetic and Evolutionary Computation, GECCO ’11 (pp. 2075–2082). New York, NY: ACM.
   Google Scholar
• Leskovec, J., Lang, K. J., & Mahoney, M. W. (2010). Empirical comparison of algorithms for network community detection. In J. F. M. Rappa, P. Jones, & S. Chakrabarti (Eds.), Proceedings of the 19th International Conference on World Wide Web (pp. 631–640). New York, NY: ACM.
   Google Scholar
• Lewis, R., Thompson, J., Mumford, C., & Gillard, J. (2012). A wide-ranging computational comparison of high-performance graph colouring algorithms. Computers & Operations Research, 39, 1933–1950.
   Web of Science ®Google Scholar
• Lü, Z., & Hao, J. K. (2010). A memetic algorithm for graph coloring. European Journal of Operational Research, 203, 241–250.
   Web of Science ®Google Scholar
• Malaguti, E., Monaci, M., & Toth, P. (2011). An exact approach for the vertex coloring problem. Discrete Optimization, 8, 174–190.
   Web of Science ®Google Scholar
• Moalic, L., & Gondran, A. (2015). The new memetic algorithm HEAD for graph coloring: An easy way for managing diversity. In G. Ochoa & F. Chicano (Eds.), Evolutionary computation in combinatorial optimization (Vol. 9026, pp. 173–183). Cham: Springer.
   Google Scholar
• Neumann, F., & Witt, C. (2010). Bioinspired computation in combinatorial optimization -- Algorithms and their computational complexity. Berlin: Springer.
   Google Scholar
• Porumbel, D. C., Hao, J. K., & Kuntz, P. (2010). A search space “cartography” for guiding graph coloring heuristics. Computers & Operations Research, 37, 769–778.
   Web of Science ®Google Scholar
• Porumbel, D. C., Hao, J. K., & Kuntz, P. (2013). Informed reactive tabu search for graph coloring. Asia-Pacific Journal of Operational Research, 30, 1350010.
   Web of Science ®Google Scholar
• Sghir, I., Hao, J.-K., Jaafar, I. B., & Ghédira, K. (2015). A distributed hybrid algorithm for the graph coloring problem. In International Conference on Artificial Evolution (Evolution Artificielle) (pp. 205–218), Cham.
   Google Scholar
• Smith, D. H., Hurley, S., & Thiel, S. U. (1998). Improving heuristics for the frequency assignment problem. European Journal of Operational Research, 107, 76–86.
   Web of Science ®Google Scholar
• Spinrad, J. P., & Vijayan, G. (1985). Worst case analysis of a graph coloring algorithm. Discrete Applied Mathematics, 12, 89–92.
   Web of Science ®Google Scholar
• Sudholt, D. (2013). A new method for lower bounds on the running time of evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 17, 418–435.
   Web of Science ®Google Scholar
• Sudholt, D., & Zarges, C. (2010). Analysis of an iterated local search algorithm for vertex coloring. In O. Cheong, K. Y. Chwa, & K. Park (Eds.), Proceedings of the 21st International Symposium on Algorithms and Computation, ISAAC ’10 (Vol. 6506, pp. 340–352). Berlin: Springer.
   Google Scholar
• Sutton, A. M., & Neumann, F. (2012). A parameterized runtime analysis of evolutionary algorithms for the Euclidean traveling salesperson problem. In Proceedings of the Twenty-sixth Conference on Artificial Intelligence, AAAI ’12 (pp. 1105–1111). Menlo Park, CA: AAAI Press.
   Google Scholar
• Titiloye, O., & Crispin, A. (2011a). Graph coloring with a distributed hybrid quantum annealing algorithm. In KES International Symposium on Agent and Multi-Agent Systems: Technologies and Applications (pp. 553–562), Berlin.
   Google Scholar
• Titiloye, O., & Crispin, A. (2011b). Quantum annealing of the graph coloring problem. Discrete Optimization, 8, 376–384.
   Web of Science ®Google Scholar
• Titiloye, O., & Crispin, A. (2012). Parameter tuning patterns for random graph coloring with quantum annealing. PLoS ONE, 7, e50060.
   PubMed Web of Science ®Google Scholar
• Witt, C. (2012). Analysis of an iterated local search algorithm for vertex cover in sparse random graphs. Theoretical Computer Science, 425, 117–125.
   Web of Science ®Google Scholar
• Wu, Q., & Hao, J. K. (2012). Coloring large graphs based on independent set extraction. Computers & Operations Research, 39, 283–290.
   Web of Science ®Google Scholar
• Yu, Y., Yao, X., & Zhou, Z.-H. (2012). On the approximation ability of evolutionary optimization with application to minimum set cover. Artificial Intelligence, 180, 20–33.
   Web of Science ®Google Scholar