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.