Facebook Instagram Twitter RSS Feed PodBean Back to top on side

Solving the Generalized Vertex Cover Problem by Genetic Algorithm

In: Computing and Informatics, vol. 29, no. 6+
M. Milanović

Details:

Year, pages: 2010, 1251 - 1265
Keywords:
Vertex cover, genetic algorithms, evolutionary approach, combinatorial optimization, graph algorithms
About article:
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.
How to cite:
ISO 690:
Milanović, M. 2010. Solving the Generalized Vertex Cover Problem by Genetic Algorithm. In Computing and Informatics, vol. 29, no.6+, pp. 1251-1265. 1335-9150.

APA:
Milanović, M. (2010). Solving the Generalized Vertex Cover Problem by Genetic Algorithm. Computing and Informatics, 29(6+), 1251-1265. 1335-9150.