A Performance Comparison of Graph Coloring Algorithms

Abstract

Graph coloring problem (GCP) is getting more popular to solve the problem of coloring the adjacent regions in a map with minimum different number of colors. It is used to solve a variety of real-world problems like map coloring, timetabling and scheduling. Graph coloring is associated with two types of coloring as vertex and edge coloring. The goal of the both types of coloring is to color the whole graph without conflicts. Therefore, adjacent vertices or adjacent edges must be colored with different colors.  The number of the least possible colors to be used for GCP is called chromatic number. As the number of vertices or edges in a graph increases, the complexity of the problem also increases. Because of this, each algorithm can not find the chromatic number of the problems and may also be different in their executing times. Due to these constructions, GCP is known an NP-hard problem. Various heuristic and metaheuristic methods have been developed in order to solve the GCP. In this study, we described First Fit (FF), Largest Degree Ordering (LDO), Welsh and Powell (WP), Incidence Degree Ordering (IDO), Degree of Saturation (DSATUR) and Recursive Largest First (RLF) algorithms which have been proposed in the literature for the vertex coloring problem and these algorithms were tested on benchmark graphs provided by DIMACS. The performances of the algorithms were compared as their solution qualities and executing times. Experimental results show that while RLF and DSATUR algorithms are sufficient for the GCP, FF algorithm is generally deficient. WP algorithm finds out the best solution in the shortest time on Register Allocation, CAR, Mycielski, Stanford Miles, Book and Game graphs. On the other hand, RLF algorithm is quite better than the other algorithms on Leighton, Flat, Random (DSJC) and Stanford Queen graphs.

Keywords

• Chromatic number,Graph coloring algorithms

References

1. [1] D. B. West, Introduction to Graph Theory, Prentice Hall, U. S. A., 588 pp, 2001.
2. [2] J. L. Gross And J. Yellen, Graph Theory and Its Applications, CRC Press, Mathematics, 600 pages, 1998.
3. [3] R. Fritsch, and G. Fritsch, The Four-Color Theorem: History, Topological Foundations and Idea of Proof, Newyork: Springer, pages 260, 1998.
4. [4] F. Ge, Z. Wei, Y. Tian, Z. Huang, Chaotic Ant Swarm for Graph Coloring , Intelligent Computing and Intelligent Systems (ICIS), IEEE International Conference, 512-516 p., 2010.
5. [5] D. J. Welsh, and M. B. Powell, An upper bound for the chromatic number of a graph and its application to timetabling problems, The Computer Journal 10 (1): 85–86, 1967.
6. [6] I. M. Díaz and P. Zabala, A Generalization of the Graph Coloring Problem, Departamento de Computacion, Universidad de Buenes Aires, 1999.
7. [7] B. H. Gwee, M. H. Limand and J. S. Ho, Solving fourcolouring map problem using genetic algorithm. In Proceedings of First New Zealand International Two-Stream Conference on Artificial Neural Networks and Expert Systems, 332-333, 1993.
8. [8] N. Chmait, and K. Challita, Using Simulated Annealing and Ant-Colony Optimization Algorithms to Solve the Scheduling Problem, Computer Science and Information Technology 1(3), 208-224, 2013.

9. [9] K. Dowsland, J. Thompson, Ant colony optimization for the examination scheduling problem, J. Oper. Res. Soc. 56, 426–438, 2005.
10. [10] G.J. Chaitin, M.A. Auslander, A.K. Chandra, J. Cocke, , M.E. Hopkins and P.W. Mark-stein, Register allocation via coloring, Comput. Lang. 6 47–57, 1981.
11. [11] F.C. Chow, J.L. Hennessy, The priority based coloring approach to register allocation, ACM Trans. Program. Lang. Syst, 501–536, 1990.
12. [12] S. Ono, R. Miyamoto, S. Nakayama, and K. Mizuno, "Difficulty estimation of number place puzzle and its problem generation support." ICCAS-SICE, 2009. IEEE, 2009.
13. [13] W. K. Hale, Frequency assignment: Theory and applications. Proceedings of the IEEE 12: 1497-1514, 1980.
14. [14] M.R. Garey and D.S. Johnson, Computers and intractability, in: A Guide to the Theoryof NP-Completeness, W.H. Freeman & Co., New York, NY, U.S.A., 1979.
15. [15] S. Mahmoudi and S. Lotfi, Modified cuckoo optimization algorithm (MCOA) to solve graph coloring problem, Applied soft computing Volume 33, 48–64, 2015.
16. [16] A. Hertz and D. de Werra, Using tabu search techniques for graph coloring, Computing 39, 345–351, 1987.
17. [17] M. Chams, A. Hertz and D. de Werra, Some experiments with simulated annealing for coloring graphs, European Journal of Operational Research, 32(2):260-266, 1987.
18. [18] S. Ahn, S. Lee, T. Chung, Modified Ant Colony System for Coloring Graphs, Information, Communications and Signal Processing, 2003 and Fourth Pacific Rim Conference on Multimedia. Proceedings of the Joint Conference of the Fourth International Conference on, IEEE, 1849 – 1853, 2003.
19. [19] H. Al-Omari and K.E. Sabri, New Graph Coloring Algorithms, American Journal of Mathematics and Statistics 2 (4): 739-741, 2006.
20. [20] F.T. Leighton, A graph coloring algorithm for large scheduling problems, J. Res.Nat. Bur. Stand. 84 489–506, 1979.
21. [21] D. Brélaz, New methods to color the vertices of a graph, Commun. ACM 22 251–256, 1979.
22. [22] DIMACS graph coloring instances. (2016) instances homepage on CMU. [online]. Available: http:mat.gsia.cmu.edu/COLOR/instances.html.
23. [23] I. C. R. Ruiz, “Gravitational Swarm for Graph Coloring”, PHD thesis, The University of the Basque Country Donostia - San Sebastian, 2012.
24. [24] D. S. Johnson and M. A. Trick, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993, vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society. 1996.
25. [25] M. Caramia and P. Dell'Olmo. A lower bound on the chromatic number of mycielski graphs. Discrete Mathematics, 235(1-3):79_86, 2001.
26. [26] B. Yılmaz, A novel meta-heuristic for graph coloring problem: simulated annealing with backtracking, Yeditepe University Graduate School Of Natural Scıences, Istanbul, 2011.