Cellular learning automata based algorithm for solving minimum vertex cover problem
Aylin Mousavian, Alireza Rezvanian, Mohammad Reza Meybodi · 2014
The minimum vertex cover of a given graph G is a set of vertices such that every vertex in G belongs either to the set or adjacent to vertices of the covering set. Finding the minimum vertex cover in an arbitrary graph is NP-Complete and several approximation algorithms have been proposed for solving this problem in graphs. In this paper, cellular learning automata based algorithm is proposed for solving the minimum vertex cover problem. In this algorithm each vertex as a cell is equipped with a learning automaton that has been influenced by adjacent cells and learning rule. This approach gradually reaches near optimal solution for minimum vertex cover and reduces the number of cells as covering set. Taking advantage of parallel implementation, proposed algorithm reduces running time in most of instances. The proposed algorithm is tested on DIMACS benchmark graphs and is compared with other well-known algorithms. Experimental results show that proposed algorithm uniformly performs efficiently and gives better results over other methods.