A New Vertex Coloring Algorithm Based on Variable Action-Set Learning Automata

Abstract

In this paper, we propose a learning automata-based iterative algorithm for approximating a near optimal solution to the vertex coloring problem. Vertex coloring is a well-known NP-hard optimization problem in graph theory in which each vertex is assigned a color so that no two adjacent ertices have the same color. Each iteration of the proposed algorithm is subdivided into several stages, and at each stage a subset of the uncolored non adjacent vertices are randomly selected and assigned the same color. This process continues until no more vertices remain uncolored. As the proposed algorithm proceeds, taking advantage of the learning automata the number of stages per iteration and so the required number of colors tends to the chromatic number of the graph since the number of vertices which are colored at each stage is maximized. To show the performance of the proposed algorithm we compare it with several existing vertex coloring algorithms in terms of the time and the number of colors required for coloring the graphs. The obtained results show the superiority of the proposed algorithm over the others.