Please use this identifier to cite or link to this item:
|Title:||Comparative analysis of Vertex Cover computation algorithms for varied graphs|
Sowmya, Kamath S.
|Citation:||International Conference on Communication and Signal Processing, ICCSP 2014 - Proceedings, 2014, Vol., , pp.1535-1539|
|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.|
|Appears in Collections:||2. Conference Papers|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.