Solving the Graph Sum Colouring Problem Using a Heuristic Algorithm

Graph sum colouring is the assignment of natural numbers to the
vertices of a simple graph so that the sum of the numbers assigned to the
vertices of the graph is minimized. Its most important application is in the
scheduling problems. Given that this is one of the NP-Hard problems, no
exact solution has been provided so far. Therefore, in this study, a hybrid
heuristic, based on the idea of identifying independent sets of graph vertices
and assigning the smallest natural number available for the largest
independent set has been developed. The proposed algorithm is tested on
graphs in well-known libraries of randomly generated graphs. The results
show the efficiency of the proposed algorithm.