Solving the Generalized Vertex Cover Problem by Genetic Algorithm

Authors

  • Marija Milanović

Keywords:

Vertex cover, genetic algorithms, evolutionary approach, combinatorial optimization, graph algorithms

Abstract

In this paper an evolutionary approach to solving the generalized vertex cover problem (GVCP) is presented. Binary representation and standard genetic operators are used along with the appropriate objective function. The experiments were carried out on randomly generated instances with up to 500 vertices and 100000 edges. Performance of the genetic algorithm (GA) is compared with CPLEX solver and 2-approximation algorithm based on LP relaxation. The genetic algorithm outperformed both CPLEX solver and 2-approximation heuristic.

Downloads

Download data is not yet available.

Author Biography

Marija Milanović

Faculty of Mathematics
University of Belgrade
Studentski trg 16/IV, 11 000 Belgrade, Serbia

Downloads

Published

2012-01-26

How to Cite

Milanović, M. (2012). Solving the Generalized Vertex Cover Problem by Genetic Algorithm. COMPUTING AND INFORMATICS, 29(6+), 1251–1265. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/142

Issue

Vol. 29 No. 6+ (2010): Computing and Informatics

Section

Articles