Comparative analysis of Vertex Cover computation algorithms for varied graphs

Abstract

There are several vertex cover algorithms proposed for the solution of well-known NP-complete class problem of computing vertex cover. The Vertex Cover problem is important to address as it has various real world applications viz. Wireless Communication Network, Airline Communication Network, Terrorist Communication Network, etc. In this paper, we present a comparative evaluation of different existing algorithms like approximation, list, greedy and Alom's for most efficiently computing vertex cover over a variety of large graphs. Our empirical study found that Alom's algorithm performs consistently better than the other algorithms for all types of graphs, regardless of their class and number of vertices in the graph, while approximation algorithms show the worst performance for very large graphs. © 2014 IEEE.