A New Ant Colony Optimization Algorithm for the Lower Bound of Sum Coloring Problem

1. Bar-Noy, A., Bellareb, M., Halldorsson, M.M., Shachnai, H., Tamir, T.: On chromatic sums and distributed resource allocation. Inf. Comput. 140(2), 183–202 (1998)

   Article  MATH  Google Scholar 

2. Bloechliger, I., Zufferey, N.: A graph coloring heuristic using partial solutions and a reactive tabu scheme. Comput. Oper. Res. 35, 960–975 (2008)

   Article  MathSciNet  MATH  Google Scholar 

3. Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)

   Article  MathSciNet  MATH  Google Scholar 

4. Cheng, C.B., Mao, C.P.: A modified ant colony system for solving the travelling salesman problem with time windows. Math. Comput. Model. 46, 1225–1235 (2007)

   Article  MathSciNet  MATH  Google Scholar 

5. Chow, F.C., Hennessy, J.L.: The priority-based coloring approach to register allocation. ACM Trans. Program. Lang. Syst. 12, 501–536 (1990)

   Article  Google Scholar 

6. Costa, D., Hertz, A.: Ants can color graphs. J. Oper. Res. Soc. 48, 295–305 (1997)

   MATH  Google Scholar 

7. de Werra, D.: An introduction to timetabling. Eur. J. Oper. Res. 19(2), 151–162(1985)

   Article  MATH  Google Scholar 

8. Dorigo, M.: Optimization, learning, and natural algorithms. Ph.D. dissertation (in Italian), Dipartimento di Elettronica, Politecnico di Milano, Italy (1992)

9. Dorigo, M., Blum, C.: Ant colony optimization theory: a survey. Theor. Comp. Sci. 344(2–3), 243–278 (2005)

   Article  MathSciNet  MATH  Google Scholar 

10. Dorigo, M., Di Caro, G.: Ant colony optimisation: a new meta-heuristic. In: Proceedings of the 1999 Congress on Evolutionary Computation, vol. 2, pp. 1470–1477 (1999)

11. Dorigo, M., Stutzle, T.: Ant Colony Optimization. MIT Press, Massachusetts Institute of Technology, Cambridge (2004)

    Book  MATH  Google Scholar 

12. Douiri, S.M., Elbernoussi, S.: New algorithm for the sum coloring problem. Int. J. Contemp. Math. Sci. 6(10), 453–463 (2011)

    MathSciNet  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

15. Gamst, A.: Some lower bounds for a class of frequency assignment problem. IEEE Trans. Veh. Technol. 35, 8–14 (1999)

    Article  Google Scholar 

16. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)

    MATH  Google Scholar 

17. Kokosinski, Z., Kawarciany, K.: On sum coloring of graphs with parallel genetic algorithms. In: ICANNGA’07, 2007, Part I, LNCS 4431, pp. 211–219 (2007)

18. Kroon, L.G., Sen, A., Deng, H., Roy, A.: The optimal cost chromatic partition problem for trees and interval graphs. In: Graph-Theoretical Concepts in Computer Science, LNCS, pp. 279–292 (1996)

19. Kubicka, E., Schwenk, A.J.: An introduction to chromatic sums. In: Proceedings of the ACM Computer Science Conference, pp. 39–45 (1989)

20. Li, Y., Lucet, C., Moukrim, A., Sghiouer, K.: Greedy Algorithms for the Minimum Sum Coloring Problem. In: International Workshop: Logistics and Transport (2009)

21. Lucet, C., Mendes, F., Moukrim, A.: An exact method for graph coloring. Comput. Oper. Res. 33(8), 2189–2207 (2006)

    Article  MathSciNet  MATH  Google Scholar 

22. Malafiejski, M.: Sum coloring of graphs. Graph Colorings, Contemp. Math. 352, 55–65 (2004)

    Article  MathSciNet  Google Scholar 

23. Moukrim, A., Sghiouer, K., Lucet, C., Li, Y.: Lower bounds for the minimal sum coloring problem. Electron. Notes Discrete Math. 36, 663–670 (2010)

    Article  Google Scholar 

24. Poorzahedy, H., Abulghasemi, F.: Application of ant system to network design problem. Transportation 32, 251–273 (2005)

    Article  Google Scholar 

25. Salari, E., Eshghi, K.: An ACO algorithm for the graph coloring problem. Int. J. Contemp. Math. Sci. 3(6), 293–304 (2008)

    MathSciNet  MATH  Google Scholar 

26. Stecke, K.: Design planning, scheduling and control problems of flexible manufacturing. Ann. Oper. Res. 3, 3–12 (1985)

    Article  Google Scholar 

27. Thomassen, C., Erdos, P., Alavi, Y., Malde, P.J., Schwenk, A.J.: Tight bounds on the chromatic sum of a connected graph. J. Graph Theory 13(3), 353–357 (1989)

    Article  MathSciNet  MATH  Google Scholar 

28. Walkowiak, K.: Graph coloring using ant algorithms. In: Proceedings of the Conference on Computer Recognition Systems KOSYR, pp. 199–204, Milkow, 28–31 May 2001

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

    Article  MathSciNet  MATH  Google Scholar 

Download references