Applying Genetic Algorithm to the Minimum Vertex Cover Problem
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Let G = (V, E) be a simple undirected graph. The Minimum Vertex Cover (MVC) problem is to find a minimum subset C of V such that for every edge, at least one of its endpoints should be included in C. Like many other graph theoretic problems this problem is also known to be NP-hard. In this paper, we propose a genetic algorithm called LeafGA for MVC problem and show the performance of the proposed algorithm by applying it to several published benchmark graphs.
Abstract
Let G = (V, E) be a simple undirected graph. The Minimum Vertex Cover (MVC) problem is to find a minimum subset C of V such that for every edge, at least one of its endpoints should be included in C. Like many other graph theoretic problems this problem is also known to be NP-hard. In this paper, we propose a genetic algorithm called LeafGA for MVC problem and show the performance of the proposed algorithm by applying it to several published benchmark graphs.
참고문헌 (7)
- Holland, J., "Adaptation in natural and artificial systems" (1975), University of Michigan Press
- S. Khuri, "An evolutionary heuristic for the minimum vertex cover problem", Proc. of the KI-94 Workshop, pp.86~90 (1994)
- I.K.Evans, "Evolutionary algorithms for vertex cover", Lecture Notes in Computer Science, 1477, pp.377~386 (1998)
- Jun He, "A comparative study of three evolutionary algorithms incorporating different amounts of domain knowledge for node covering problem", IEEE Transactions on Systems Man and Cybernetics, 35(2), pp.266~271 (2005)
- R.Motwani, "Lecture notes on approximation algorithms: Volume I, Tech. Rep. CS-TR-92-1435, Stanford University, Department of Computer Science, Stanford University", ~ (1992)
- "BHOSLIB: Benchmarks with hidden optimum solutions for graph problems (maximum clique, maximum independent set, minimum vertex cover and vertex coloring) – hiding exact solutions in random graphs"[URL]
- Gilmour, S., "Kernelization as heuristic structure for the vertex cover problem", In proceedings of the Third Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS 2006) (2006)