| Paper title: |
Heuristic Algorithm for Graph Coloring Based On Maximum Independent Set |
| Published in: | Issue 2, (Vol. 6) / 2012 |
| Publishing date: | 2011-10-24 |
| Pages: | 19-23 |
| Author(s): | ALMARA’BEH Hilal, SULEIMAN Amjad |
| Abstract. | A number of heuristic algorithms have been developed for the graph coloring problem, but unfortunately, on any given instance, they may produce colorings that are very far from optimal. In this paper we investigated and introduce a three heuristics algorithm to color a graph based on a maximum independent set. The select a node with minimum and maximum degree consecutively (Min_Max) algorithm is implemented, tested and compared with select a node with minimum degree first (SNMD), select a node with maximum degree first (SNXD) in terms of CPU time and size of graph with different densities (0.1,0.2,…,0.9 ). The result indicated that the Min_Max algorithm and SNXD is better than SNMD based on the time of first maximum independent set, running time of CPU and the number of coloring nodes. |
| Keywords: | Maximum Independent Set, Heuristic Algorithm, Adjacent Nodes, Independent Set. |
| References: | 1. Manuel Laguna, Tabu Search with Simple Ejection Chain for Coloring Graphs. Leeds School of Business, University of Colorado, Boulder, CO 80309-0419, USA, February 14, 2002. 2. Johnson, D.S.,"Worst-case behavior of graph coloring algorithm",Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing,Utilitas Mathematica Publishing Winnipeg, Canada (1974) 513-528. 3. Leighton,F.T.A Grapg Coloring Algorithm for large Scheduling Problems,J.Res. Nat. Bur. Standard, 84,(1979) 789-506. 4. D.S Johnson, C.A. Aragon, L.A. Mcgeoch and C. Schevon, Optimization by Simulated Annealing: An Experimental Evaluation – Part II ( Graph Coloring and Number Partitioning), Operations Research, 31,(1991) 378-406. 5. S. Kirkpatrick, C.D Gelatt Jr. and M.P. Vecchi Optimaization by Simulated Annealing, Science, 220,(1983) 61-680. 6. F.Golver and M.Laguna, Tabu Search, Kluwer Academic Publishers, 1997. 7. J.H. Holland, Adaptation in natural language and Artificial Systems, University of Michigan Press, Ann Arbor, MI, 1975. 8. T.A.R.E Feo, and M.G.C Resende, A Probabilistic Heuristic for Computationally Diffecult Set Covering Problem, Operations Research Letters,8,(1989) 67-71 9. T.A.R.E Feo, and M.G.C Resende, Greedy Randomize Adaptive Search Procedures,Journal Of Global Optimization 2,(1995) 1-27 10. M.. Chams, A. Hertz and D. de Werra, Some Experiments with Simulated Annealing for Coloring Graphs, European Journal Of Operational Research,32,(1987) 260-266. 11. Al-Jaber, A. and Sharieh, A. Algorithms Based on Weight Factors for Maximum Independent Set. Jordan: University of Jordan, 1999. 12. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the theory of NP-Completeness, W.H. Freeman and Co., Francisco, 1979 |
| Back to the journal content | |
