Graph coloring problem is one of the classical combinatorial optimization problems. This problem consists in finding the minimal number of colors in which it is possible to color vertices of a graph so that any two adjacent vertices are colored in different colors. The graph coloring problem has a wide variety of applications including timetabling problems, processor register allocation problems, frequency assignment problems, data clustering problems, traffic signal phasing problems, maximum clique problem, maximum independent set problem, minimum vertex cover problem and others. In this paper a new efficient heuristic algorithm for the graph coloring problem is presented. The suggested algorithm builds the same coloring of a graph as does the widely used greedy sequential algorithm in which at every step the current vertex is colored into minimal feasible color. Computational experiments show that the presented algorithm performs graph coloring much faster in comparison with the standard greedy algorithm. The speedup reaches 5,6 times for DIMACS graphs.
In this paper a fast greedy sequential heuristic for the vertex colouring problem is presented. The suggested algorithm builds the same colouring of the graph as the well-known greedy sequential heuristic in which on every step the current vertex is coloured in the minimum possible colour. Our main contributions include introduction of a special matrix of forbidden colours and application of efficient bitwise operations on bit representations of the adjacency and forbidden colours matrices. Computational experiments show that in comparison with the classical greedy heuristic the average speedup of the developed approach is 2.6 times on DIMACS instances.