A New Ant Colony Algorithm for Minimum Vertex Cover Problem

In this paper, we propose a meta-heuristic based on Ant Colony Optimization (ACO) approach, called MVC-AC, to find approximate solutions to the minimum vertex cover problem which is an important optimization problem in graph theory with many applications. We compare our algorithm with two existing algorithms which are based on Genetic Algorithms (GAs) as well as its testing on a variety of benchmarks. Computational experiments evidence that the ACO algorithm demonstrates much effectiveness and consistency for solving the minimum vertex cover problem.

Keywords:

Algorithmic Graph Theory , Combinatorial Optimization , Minimum Vertex Cover Problem , Ant Colony Optimization Algorithms