Comparative Analysis of Vertex Cover Computation Algorithms for Varied Graphs

被引：0

作者：

Patel, Smit ^{[1
]}

Kamath, Sowmya S. ^{[1
]}

机构：

[1] Natl Inst Technol Karnataka, Dept Informat Technol, Surathkal, India

来源：

2014 INTERNATIONAL CONFERENCE ON COMMUNICATIONS AND SIGNAL PROCESSING (ICCSP) | 2014年

关键词：

Approximation Algorithm; Clever Greedy Algorithm; Graph Theory; Greedy Algorithm; Lists Algorithm Vertex Cover Problem;

D O I：

暂无

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

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.

引用

页数：5