Solving Minimum Vertex Cover Problem Using Learning Automata
This work addresses a fundamental combinatorial optimization problem for graph theory and algorithm design, but it appears incremental as it applies an existing learning automata framework to a known problem.
The paper tackles the NP-hard minimum vertex cover problem by proposing a learning automaton-based algorithm that assigns each vertex an automaton to iteratively minimize the candidate cover set, and experimental results on the DIMACS dataset show it significantly outperforms conventional methods.
Minimum vertex cover problem is an NP-Hard problem with the aim of finding minimum number of vertices to cover graph. In this paper, a learning automaton based algorithm is proposed to find minimum vertex cover in graph. In the proposed algorithm, each vertex of graph is equipped with a learning automaton that has two actions in the candidate or non-candidate of the corresponding vertex cover set. Due to characteristics of learning automata, this algorithm significantly reduces the number of covering vertices of graph. The proposed algorithm based on learning automata iteratively minimize the candidate vertex cover through the update its action probability. As the proposed algorithm proceeds, a candidate solution nears to optimal solution of the minimum vertex cover problem. In order to evaluate the proposed algorithm, several experiments conducted on DIMACS dataset which compared to conventional methods. Experimental results show the major superiority of the proposed algorithm over the other methods.