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 100 000 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.
Keywords
Cite this article
@article{cai-18137,
author = {Marija Milanović},
title = {Solving the Generalized Vertex Cover Problem by Genetic Algorithm},
journal = {Computing and Informatics},
volume = {29},
number = {6+},
pages = {1251--1265},
year = {2010},
issn = {1335-9150},
url = {https://cai.type.sk/content/2010/6%2B/solving-the-generalized-vertex-cover-problem-by-genetic-algorithm/}
}
TY - JOUR AU - Marija Milanović TI - Solving the Generalized Vertex Cover Problem by Genetic Algorithm JO - Computing and Informatics VL - 29 IS - 6+ SP - 1251 EP - 1265 PY - 2010 SN - 1335-9150 UR - https://cai.type.sk/content/2010/6%2B/solving-the-generalized-vertex-cover-problem-by-genetic-algorithm/ KW - Vertex cover KW - genetic algorithms KW - evolutionary approach KW - combinatorial optimization KW - graph algorithms ER -
Milanović, M. (2010). Solving the Generalized Vertex Cover Problem by Genetic Algorithm. Computing and Informatics, 29(6+), 1251–1265. https://cai.type.sk/content/2010/6%2B/solving-the-generalized-vertex-cover-problem-by-genetic-algorithm/