G = (V, E) 를 단순 무방향성 그래프라 하자. Minimum Vertex Cover (MVC) 문제는 C 를 V 의 부분 집합이라 할 때 모든 간선들이 C 내의 최소 한 개 정점과 인접하게 되는 최소 집합 C 를 계산하는 것이다. 다른 많은 그래프 이론 문제와 마찬가지로 본 문제도 NP-hard 문제임이 증명되었다. 본 논문에서는 MVC 문제를 위한 LeafGA 라는 새로운 유전 알고리즘을 제시하며 또한 제시된 알고리즘을 널리 알려 진 기준 그래프들에 적용함으로써 그 효용성을 보인다.
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.
