Applying Genetic Algorithm to the Minimum Vertex Cover Problem


The KIPS Transactions:PartB , Vol. 15, No. 6, pp. 609-612, Dec. 2008
10.3745/KIPSTB.2008.15.6.609,   PDF Download:

Abstract

Let G = (V, E) be a simple undirected graph. The Minimum Vertex Cover (MVC) problem is to find a minimum subset C of V such that for every edge, at least one of its endpoints should be included in C. Like many other graph theoretic problems this problem is also known to be NP-hard. In this paper, we propose a genetic algorithm called LeafGA for MVC problem and show the performance of the proposed algorithm by applying it to several published benchmark graphs.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
K. H. Han and C. S. Kim, "Applying Genetic Algorithm to the Minimum Vertex Cover Problem," The KIPS Transactions:PartB , vol. 15, no. 6, pp. 609-612, 2008. DOI: 10.3745/KIPSTB.2008.15.6.609.

[ACM Style]
Keun Hee Han and Chan Soo Kim. 2008. Applying Genetic Algorithm to the Minimum Vertex Cover Problem. The KIPS Transactions:PartB , 15, 6, (2008), 609-612. DOI: 10.3745/KIPSTB.2008.15.6.609.