New variable neighborhood search method for minimum sum coloring problem on simple graphs

Document Type : Research Article

Authors

• Kh. Erfani
• S. Rahimi
• J. fathali

Shahrood University of Technology, Shahrood

10.22067/ijnao.v8i2.61465

Abstract

The minimum sum coloring problem (MSCP) is to find a legal vertex coloring for G using colors represented by natural numbers (1,2, . . .) such that the total sum of the colors assigned to the vertices is minimized. The aim of this paper is to present the skewed variable neighborhood search (SVNS) for this problem based on a new structure of neighborhoods. To increase the speed of the neighborhood search process, we present the new concepts of holder vertex and set. Tested on 23 commonly used benchmark instances, our algorithm shows acceptable competitive performance with respect to recently proposed heuristics.

Keywords

• Minimum sum coloring
• Variable neighborhood search
• Skewed variable neighborhood search
• Chromatic sum
• Holder vertex
• Holder set
• Reducer set

20.1001.1.24236977.2018.8.2.3.1

---

References

1. Benlic, U. and Hao, J. K. A study of breakout local search for the minimum sum coloring problem, pp. 128–137, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012.

2. Bouziri, H. and Jouini, M. A tabu search approach for the sum coloring problem, Electronic Notes in Discrete Math. 36 (2010) 915–922.

3. Burke, E. K., McCollum, B., Meisels, A., Petrovic, S. and Qu, R. A graph based hyper-heuristic for educational timetabling problems, Eur. J. Oper. Res. 176 (2007), no. 1, 177 – 192.

4. de Werra, D., Eisenbeis, Ch.,Lelait, S. and Marmol, B.On a graph- theo retical model for cyclic register allocation, Discrete Appl. Math. 93 (1999), no. 23, 191 – 203.

5. Douiri S.M. and Elbernoussi, S. New algorithm for the sum coloring problem, Int. J. Contemporary Math. Sci. 6 (2011) no. 9-12, 181–192.

6. Douiri S. M. and Elbernoussi, S. A new ant colony optimization algorithm for the lower bound of sum coloring problem, J. Math. Model. Algorithms 11 (2012), no. 2, 181–192.

7. Erdos, P., Kubicka, E. and Schwenk, A. J. Graphs that require many colors to achieve their chromatic sum, In Proceedings of the Twentieth South-eastern Conference on Combinatorics Graph Theory and Computing (Boca Raton, FL), vol. 71, 1990, pp. 17–28.

8. Gamache, M., Hertz, A. and Ouellet, J. O. A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding, Comput. Oper. Res. 34 (2007), no. 8, 2384–2395.

9. Garey, M. R. and Johnson, D. S. Computers and intractability; a guide to the theory of np-completeness, W. H. Freeman & Co., New York, NY, USA, 1990.

10. Glass, C. A. Bag rationalisation for a food manufacturer, J. Oper. Res. Soc. 53 (2002), no. 5, 544–551.

11. Hajiabolhassan, H.,Mehrabadi, M.L. and Tusserkani, R. Minimal color ing and strength of graphs, Discrete Math. 215 (2000), no. 1, 265 – 270.

12. Hajiabolhassan, H.,Mehrabadi, M. L. and Tusserkani, R. Tabular graphs and chromatic sum, Discrete Math. 304 (2005), no. 1-3, 11–22.

13. Hansen, P. and Mladenovic, N. Variable neighborhood search: Principles and applications, Eur. J. Oper. Res. 130 (2001) no. 3, 449–467.

14. Hao J. -K. and Wu, Q. Improving the extraction and expansion method for large graph coloring, Discrete Appl. Math. 160 (2012), no. 1617, 2397 – 2407.

15. Helmar, A. and Chiarandini, M. A local search heuristic for chromatic sum, Proceedings of the 9th Metaheuristics International Conference, MIC 2011 (L. D. Gaspero, A. Schaerf, and T. Stutzle, eds.), 2011, pp. 161–170.

16. Jiang, T. and West, D. B. Coloring of trees with minimum sum of colors, J. Graph Theory 32 (1999), no. 4, 354–358.

17. Jin, Y.,Hao, J. K. and Hamiez, J. P. A memetic algorithm for the minimum sum coloring problem, Comput. Oper. Res. 43 (2014), 318 – 327.

18. Jin, Y. and Hao, J. -K. Hybrid evolutionary search for the minimum sum coloring problem of graphs, Inf. Sci. 352 (2016), no. C, 15–34.

19. Kokosi´nski Z. and Kwarciany, K. On sum coloring of graphs with parallel genetic algorithms, pp. 211–219, Springer Berlin Heidelberg, Berlin, Heidelberg, 2007.

20. Kroon, L. G., Sen, A. , Deng, H. and Roy, A. The optimal cost chromatic partition problem for trees and interval graphs, pp. 279–292, Springer Berlin Heidelberg, Berlin, Heidelberg, 1997.

21. Kubicka, E. The chromatic sum of a graph, Ph.D. thesis, Western Michigan University, Michigan, 1989.

22. Kubicka, E. and Schwenk, A. J. An introduction to chromatic sums, Proceedings of the 17th Conference on ACM Annual Computer Science Conference (New York, NY, USA), CSC ’89, ACM, 1989, pp. 39–45.

23. Li, Y. ,Lucet, C., Moukrim, A. andSghiouer, K. Greedy Algorithms for the Minimum Sum Coloring Problem, Logistique et transports (Sousse,Tunisia), March 2009, pp. LT–027.

24. Malafiejski, M. Sum coloring of graphs, pp. 55–65, AMS, Poland, 2004.

25. Mladenovic, N. and Hansen, P. Variable neighborhood search, Comput. Oper. Res. 24 (1997) no.11, 1097–1100.

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

27. Papadimitriou, C. H. and Steiglitz, K. Combinatorial optimization: Algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1982.

28. Smith, D.H., Hurley, S. and Thiel, S.U. Improving heuristics for the frequency assignment problem, Eur. J. Oper. Res. 107 (1998), no. 1, 76 –86.

29. Stecke, K. E. Design, planning, scheduling, and control problems of exible manufacturing systems, Ann. Oper. Res. 3 (1985), no. 1, 1–12.

30. Supowit, K. J. Finding a maximum planar subset of a set of nets in a channel, Trans. Comp.-Aided Des. Integ. Cir. Sys. 6 (2006), no. 1, 93–94.

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

32. Wang, Y., Hao, J. K.,Glover, F. and Lu, Zh. Solving the minimum sum coloring problem via binary quadratic programming, CoRR abs/1304.5876 (2013).

33. Wu Q. and Hao, J. -K. An effective heuristic algorithm for sum coloring of graphs, Comput. Oper. Res. 39 (2012), no. 7, 1593 – 1600.

34. Wu Q. and Hao, J. -K. Improved lower bounds for sum coloring via clique decomposition, CoRR abs/1303.6761 (2013).