Academic Journals Database
Disseminating quality controlled scientific knowledge

Harnessing Genetic Algorithm for Vertex Cover Problem

Author(s): Harsh Bhasin | Geetanjli Ahuja

Journal: International Journal on Computer Science and Engineering
ISSN 0975-3397

Volume: 4;
Issue: 2;
Start page: 218;
Date: 2012;
VIEW PDF   PDF DOWNLOAD PDF   Download PDF Original page

Keywords: Genetic Algorithms | NP Hard Problem | Artificial Intelligence | Vertex Cover Problem | Non Deterministic Problems.

The problem of finding a minimum vertex cover is an NP hard optimization problem. Some approximation algorithms for the problem have been proposed but most of them are neither optimal nor complete. The work proposes the use of the theory of natural selection via Genetic Algorithms (GAs) for solving the problem. The proposed work has been tested for some constrained inputs and the results wereencouraging. The paper also discusses the application of genetic algorithms to the solution and the requisite analysis. The approach presents a Genetic Algorithms based solution to a problem.

Tango Jona
Tangokurs Rapperswil-Jona

     Affiliate Program