Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 1

NP - complete problem Related Publications

1 Optimization of Unweighted Minimum Vertex Cover

Authors: S. Balaji, V. Swaminathan, K. Kannan

Abstract:

The Minimum Vertex Cover (MVC) problem is a classic graph optimization NP - complete problem. In this paper a competent algorithm, called Vertex Support Algorithm (VSA), is designed to find the smallest vertex cover of a graph. The VSA is tested on a large number of random graphs and DIMACS benchmark graphs. Comparative study of this algorithm with the other existing methods has been carried out. Extensive simulation results show that the VSA can yield better solutions than other existing algorithms found in the literature for solving the minimum vertex cover problem.

Keywords: approximation algorithms, vertex support, vertex cover, NP - complete problem

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2153