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 112
- Downloads 0
Ruling the Remoteness of Associates and Kin Using Cellular hone with Latitude Radius Algorithm
LBS are the mobile services in which the user location nformation is used to provide a service. Providing Location Based Service (LBS) using Global Positioning System (GPS) as a location provider. The main objective of...
A Denoising Filter Design based on No-Reference Image Content Metric
DIGITAL images are subject to a wide variety of distortions during acquisition, processing, compression, storage, transmission and reproduction. Any of these may result in degradation of their visual quality. Hence, ther...
An Effect of Route Caching Scheme in DSR for Vehicular Adhoc Networks
Routing is one of the most significant challenges in Vehicular ad hoc networks and is critical for the basic network operations. Nodes (vehicles) in a Vehicular ad hoc network are allowed to move in an uncontrolled manne...
A New Approach for Designing Cryptographic Systems based on Feistel Structure
Many Classical and modern cryptographic algorithms have been developed by the Cryptographers to facilitate data security operations. Classical ciphers are not being widely used because of limited key space. Public key cr...
PRIORITY BASED UPLINK SCHEDULER FOR IEEE 802.16 NETWORKS
IEEE 802.16, the standard for fixed, portable and mobile Broadband Wireless Access (BWA) systems, is promising to support different classes of traffic with Quality of Service (QoS). The Medium Access Control (MAC) protoc...