Applying Genetic Algorithm to the Minimum Vertex Cover Problem 


Vol. 15,  No. 6, pp. 609-612, Dec.  2008
10.3745/KIPSTB.2008.15.6.609


PDF
  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
  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.

Forms

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)

Old Journals

Indexing

All publications of TKIPS is indexed in DOI, EBSCO, Google Scholar, Crossref, and CrossCheck.

TKIPS is also selected as the Journal for Accreditation by NRF (National Research Foundation of Korea).

Related Journals