A NEW APPROACH TO THE VERTEX COLORING PROBLEM

作者：Torkestani Javad Akbari^*

来源：Cybernetics and Systems, 2013, 44(5): 444-466.

DOI：10.1080/01969722.2013.803391

• combinatorial optimization problem
• graph coloring problem
• learning automata
• vertex coloring problem

The vertex coloring problem is a well-known classical optimization problem in graph theory in which a color is assigned to each vertex of the graph in such a way that no two adjacent vertices have the same color. The minimum vertex coloring problem is known to be an NP-hard problem in an arbitrary graph, and a host of approximation solutions are available. In this article, a learning automata-based approximation algorithm is proposed to solve the minimum vertex coloring problem. The proposed algorithm iteratively finds the different possible colorings of the graph and compares it at each stage with the best coloring found so far. If the number of distinct colors in the chosen coloring is less than that of the best coloring, the chosen coloring is rewarded; otherwise, it is penalized. Convergence of the proposed algorithm to the optimal solution is proven. The proposed vertex coloring algorithm is compared with the well-known coloring techniques and the results show the superiority of the proposed algorithm over the others both in terms of the color set size and running time of algorithm.

• 出版日期2013-7-4