An Efficient EA with Multipoint Guided Crossover for Bi-objective Graph Coloring Problem

1. Burke, E., Petrovic, S.: Recent research directions in automated timetabling. European J. operation research 140(2), 266–280 (2002)

   Article  MATH  Google Scholar 

2. Davis, T.: The mathematics of sudoku (2010), http://www.geometer.org/mathcircles/sudoku.pdf

3. Garey, M.R., Johnson, D.S., So, H.C.: An application of graph coloring to printed circuit testing. IEEE Transactions on Circuits and Systems 23(10), 591–599 (1976)

   Article  MathSciNet  MATH  Google Scholar 

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

   Chapter  Google Scholar 

5. Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J. Computer and System Sciences 57(2), 187–199 (1998)

   Article  MathSciNet  MATH  Google Scholar 

6. Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing 3(6), 103–128 (2007)

   Article  MathSciNet  MATH  Google Scholar 

7. Brelaz, D.: New methods to color the vertices of a graph. Commun. ACM 22(4), 251–256 (1979)

   Article  MathSciNet  MATH  Google Scholar 

8. Caramia, M., Dell’Olmo, P.: Bounding vertex coloring by truncated multistage branch and bound. Networks 44(4), 231–242 (2004)

   Article  MathSciNet  MATH  Google Scholar 

9. Mehrotra, A., Trick, M.A.: A column generation approach for graph coloring. J. Computing (JOC) 8(4), 344–354 (1996)

   MATH  Google Scholar 

10. Zoellner, J., Beall, C.: A breakthrough in spectrum conserving frequency assignment technology. IEEE Trans. Electromag. Compact. 19(3), 313–319 (1977)

    Article  Google Scholar 

11. Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417–427 (1983)

    Article  MathSciNet  MATH  Google Scholar 

12. Marino, A., Prugel-Bennett, A., Glass, C.A.: Improving graph coloring with lin-ear programmng and genetic algorithms. In: Miettinen, K., Makela, M., Toivanen, J. (eds.) Proc. Evolutionary Algorithms in Engineering and Computer Science (EU-ROGEN), Jyvaskyld, Finland, pp. 113–118. John Wiley & Sons, Chichester (1999)

    Google Scholar 

13. Al-Omari, H., Sabri, K.E.: New graph coloring algorithms. J. Mathematics and Statistics, 739–741 (2006)

    Google Scholar 

14. Croitoru, C., Luchian, H., Gheorghies, O., Apetrei, A.: A new genetic graph coloring heuristic. In: Computational Symphosium on Graph Coloring and its Generalizations, pp. 63–74 (2002)

    Google Scholar 

15. Drechsler, N., Gunther, W., Drechsler, R.: Efficient graph coloring by evolutionary algorithms. In: Reusch, B. (ed.) Proc. Int. Conf. Computational Intelligence, Theory and Applications, pp. 30–39. Springer, London (1999)

    Google Scholar 

16. Galinier, P., Hao, J.K.: Hybrid evolutionary algorithms for graph coloring. J. Combinatorial Optimization 3(4), 379–397 (1999)

    Article  MathSciNet  MATH  Google Scholar 

17. Han, L., Han, Z.: A novel bi-objective genetic algorithm for the graph coloring problem. In: Proc. Int. Conf. Computer Modeling and Simulation, Sanya, Chaina, pp. 3–6. IEEE Press, India (2010)

    Google Scholar 

18. Huang, F., Chen, G.: A symmetry-breaking approach of the graph coloring problem with gas. In: Miettinen, K., Makela, M.M., Toivanen, J. (eds.) Proc. Int. Conf. Computer Supported Cooperative Work in Design, pp. 717–719. IEEE Press, Xiamen (2004)

    Google Scholar 

19. Kumar, R., Tolay, P., Tiwary, S.: Enhancing solution quality of the biobjective graph coloring problem using hybridization of EA. In: Köppen, M., et al. (eds.) Proc. Genetic and Evolutionary Computation Conference (GECCO), pp. 547–554. ACM Press, Atlanta (2008)

    Chapter  Google Scholar 

20. Eiben, A.E., van der Hauw, J.K.: Graph coloring with adaptive genetic algorithms. Technical Report TR 96-11, Leiden University (1996)

    Google Scholar 

21. Jazkiewicz, A.: Genetic local search for multiobjective combinatorial optimization. European J. Operational Research 137(1), 50–71 (2002)

    Article  Google Scholar 

22. Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6(2), 182–197 (2002)

    Article  Google Scholar 

23. Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation 11(6), 712–731 (2007)

    Article  Google Scholar 

24. Deb, K., Jain, S.: Running performance metrics for evolutionary multiobjective optimization. In: Wang, L., Tan, K.C., Furuhashi, T., Kim, J.H., Yao, X. (eds.) Proc. Simulated Evolution And Learning (SEAL), Orchid Country Club, Singapore, pp. 13–20. ACM Press, New York (2002)

    Google Scholar 

25. Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. John Wiley & Sons, Chichester (2001)

    MATH  Google Scholar 

26. Zitzler, E.: Evolutionary algorithms for multiobjective optimization: methods and applications. PhD thesis, Swiss Federal Institute of Technology Zurich (1999)

    Google Scholar 

27. Knowles, J.D., Corne, D.W.: On metrics for comparing nondominated sets. In: Proc. Congress Evolutionary Computation (CEC), Honolulu, Hawaii, pp. 711–716. IEEE Press, Los Alamitos (2002)

    Google Scholar 

Download references