초록 close

본 논문은 지금까지 NP-완전인 난제로 알려진 최소 정점 피복 문제 (Minimum Vertex Cover Problem, MVCP)를 선형시간 복잡도로 해결한 알고리즘을 제안하였다. 탐욕 알고리즘은 가장 간단한 MVCP 알고리즘이나 항상 최적해를 얻지 못하는 단점을 갖고 있다. 탐욕 알고리즘은 최대 차수 를 갖는 정점 를 MVC 집합 에 포함시키는 방법으로 반드시 의 원소 개수 회를 수행한다. 본 논문에서는 의 반대 개념인 최소 차수 를 가진 정점 의 모든 인접 정점 를 동시에 MVC 집합 에 포함하는 알고리즘을 제안하였다. 제안된 알고리즘을 22개의 다양한 그래프에 적용한 결과 항상 최적해를 구하는데 성공하였을 뿐 아니라 최대 독립집합 (Maximum Independent Set, MIS)의 원소 개수 보다 작은 알고리즘 수행 횟수로 단축시키는 효과를 얻었다. 결국, 제안된 최소차수 인접정점 알고리즘은 MVCP의 해를 도출하는 일반적인 알고리즘으로 적용할 수 있을 것이다.


This paper introduces an algorithm that solves Minimum Vertex Cover Problem (MVCP), which by far has been known as NP-complete problem, with linear time complexity. The Greedy algorithm, though being the simplest MVCP algorithm, has not always been successful in obtaining the optimal solution. This Greedy algorithm subsumes the vertex with the maximum degree into the set of MVC, and this is necessarily performed times, which is the cardinality of the set . This paper proposes the reverse-concept algorithm using minimum degree , whereby all the adjacent vertices of the minimum degree vertex satisfying the above-mentioned criterion are conjunctly subsumed into the set of MVC. When applied to 22 different graphs, the proposed algorithm not only successfully obtained the optimal solution but also did so within the number of trials less than , which is in turn the cardinality of the Maximum Independent Set (MIS). Consequently, the proposed adjacent vertices of minimum degree vertex algorithm could be employed as the generalized algorithm for solving the MVCP.