Harnessing Genetic Algorithm for Vertex Cover Problem
Journal Title: International Journal on Computer Science and Engineering - Year 2012, Vol 4, Issue 2
Abstract
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 were encouraging. 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.
Authors and Affiliations
Harsh Bhasin , Geetanjli Ahuja
Keywords
Related Articles
- EP ID EP145498
- DOI -
- Views 117
- Downloads 0
A Model Driven approach for Applicationspecific Mismatch Detection
Several large-scale systems are developed in modules that are assembled together to deliver a desired functionality. The modules developed in isolation may not implement the desired requirements. It creates several probl...
The comparative cost analysis of EAP Re-authentication Protocol and EAP TLS Protocol
the Extensible Authentication Protocol (EAP) is a generic ramework supporting multiple types of authentication ethods. In systems where EAP is used for authentication, it is desirable to not repeat the entire EAP excha...
Integral System for Automation of Education Board and IT Association using Cloud and Mobilink.
Most of the educational boards and IT associates still use traditional and inefficient intellectual E-administration system for communicating with their valued clients. The clients may include the students in case of edu...
CHARACTER BASED WEIGHTED SUPPORT THRESHOLD LGORITHM USING MULTI CRITERIA DECISION MAKING TECHNIQUE
An association rule technique generally used to generate requent itemsets from databases and generates association rules by considering each item in the datasets. However, the values of items are different in many aspec...
Product Assembly Sequence Optimization Based on Genetic Algorithm
Genetic algorithm (GA) is a search technique used in computing to find approximate solution to optimization and search problem based on the theory of natural selection. This study investigates the application of GA in op...