Minimum Vertex Dominating Set Algorithm Using Maximum Degree Vertex Adjacent to Minimum Degree Vertex Selection Method

본 논문은 지금까지 NP-완전 문제로 다항시간 알고리즘이 존재하지 않는 지배집합 문제에 대해 다항시간으로 해를 구할 수 있는 알고리즘을 제안하였다. 제안된 알고리즘은 주어진 그래프 G(V, E)에 대해 최소 차수정점 u의 인접 정점들 중에서 최대 차수 정점 v 를 지배집합 D에 추가하는 단순한 방법을 제안하였다. 제안된 알고리즘과 집합 피복 문제의 해를 구하는 탐욕 알고리즘을 11개의 정점 지배집합 실험 사례들에 적용하였다. 탐욕 알고리즘은 3개 문제에서 최적 해를 찾는데 실패하였으나 제안된 알고리즘은 11개 모든 문제에서 최적해를 찾을 수 있었다. 결국, 정점 최소 독립 지배집합 문제는 NP-완전 문제가 아니라 P-문제가 될 수 있음을 보였다.