최소 차수 정점에 인접한 최대 차수 정점 선택 방법을 적용한 정점 최소 지배집합 알고리즘

다국어 초록 (Multilingual Abstract)

This paper proposes a polynomial time algorithm to Dominating Set problem, which thus far has been known to be NP-complete. From a given graph G(V, E), the proposed algorithm carries out two simple steps: selecting the maximum degree vertex v among all the vertices adjacent to the minimum degree vertex u; and assigning this to the Dominating Set D In this paper, both the suggested algorithm and Greedy algorithm - which is known to solve set cover problem - have been applied to 11 various vertex dominating set problems. Whereas Greedy algorithm has failed to find the optimal solution for 3 of these problems, the suggested algorithm has yielded the optimal solution for all the cases. This thus proves that the vertex dominating set problem could be P-problem rather than NP-complete.

참고문헌 (Reference)

1 이상운, "최소차수 인접 정점을 적용한 최소 정점 피복 문제 알고리즘" 한국정보기술학회 10 (10): 159-166, 2012

2 M. Pei, "Two Families of NP-Complete Problems" University of Waterloo 2003

3 V. N. Raghavan., "Simple and Efficient Backbone Algorithm for Calcurating Connected Dominating Set in Wireless Adhoc Networks" 2 (2): 732-739, 2007

4 Wikipedia, "Set Cover Problem" Wikimedia Foundation Inc.

5 M. A. Henning., "Remarks about Disjoint Dominating Sets"

6 A. Desrochers, "Island Network Analysis: MSTs and Dominating Sets" Saint Michael's College 2004

7 J. Wu., "Extended Multipoint Relays to Determine Connected Dominating Sets in MANETs" 621-630, 2004

8 J. Wu., "Extended Dominating Set and Its Applications in Ad Hoc Networks Using Cooperative Communi-cation" 17 (17): 1-14, 2006

9 J. Wu., "Domination and It's Application in Ad Hoc Wireless Networks with Undirectional Links" 189-197, 2000

10 A. Schumacher, "Dominating-set-based Routing in Ad Hoc Networks"

11 Wikipedia, "Dominating Set" Wikimedia Foundation Inc.

12 M. Garey., "Computers and Intractability : A Guide to the Theory of NPCompleteness" W. H. Freeman 1979

13 V. K. Wan., "CS 105 : Algorithms-Set Cover and Application to Shortest Superstring" Computer Science, Darmouth Collage 2005

14 W. C. K. Yen, "Bottleneck Domination and Bottleneck Independent Domination on Graphs" 18 (18): 311-331, 2002

15 Y. P. Chen., "Approximating Minimum Size Weakly-Connected Dominating Sets for Clustering Mobile Ad Hoc Networks" 165-172, 2002

16 M, "Approximability of Optimization Problems: Set Cover, Minimum Multicut" MIT 2009

17 I. Sadeghi, "An Introduction to Approximation Algorithms"

18 M. A. Trick, "A Tutorial on Integer Programming" The Operations Research Faculty of GSIA 1997

19 A. S. K. Pathan., "A Key-Predistribution-Based Weakly Connected Dominating Set for Secure Clustering in DSN" 4208 : 270-279, 2006

20 L. Ruan., "A Greedy Approximation for Minimum Connected Dominating Sets" 329 (329): 325-330, 2004