Solving the Bandwidth Multicoloring Problem: A Cellular Learning Automata Approach

In this paper, an approximation algorithm based on Irregular Cellular Learning Automata (ICLA) is proposed for solving the bandwidth coloring and bandwidth multicoloring problems. In the proposed algorithm, the multicoloring problem is first simplified as a vertex coloring problem, where each vertex is colored by only one color. To do so, the input graph must be transformed into a base graph. Then, a learning automaton is assigned to each vertex of the resultant graph. At each stage, each learning automaton randomly chooses one of its action according to its action probability vector.