지배집합 알고리즘

다국어 초록 (Multilingual Abstract)

This paper proposes a linear-time algorithm that has been designed to obtain an accurate solution for Dominating Set (DS) problem, which is known to be NP-complete due to the deficiency of polynomial-time algorithms that successfully derive an accurate solution to it. The proposed algorithm does so by repeatedly assigning vertex v with maximum degree Δ(G)among vertices adjacent to the vertex v with minimum degree Δ(G) to Minimum Independent DS (MIDS) as its element and removing all the incident edges until no edges remain in the graph. This algorithm finally transforms MIDS into Minimum DS (MDS) and again into Minimum Connected DS (MCDS) so as to obtain the accurate solution to all DS-related problems. When applied to ten different graphs, it has successfully obtained accurate solutions with linear time complexity O(n). It has therefore proven that Dominating Set problem is rather a P-problem.

참고문헌 (Reference)

1 C. W. Yi, "Wireless Communication Optimization" National Chiao Tung University 2008

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

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

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

5 M. Morgan, "Optimisaion Techniques for Wireless Networks" 339-346, 2006

6 Y. P. Chen, "Maintaining Weakly-connected Dominating Sets for Clustering Ad Hoc Networks" 3 (3): 629-642, 2005

7 A. Wiese, "Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs" School of Computer Science, CarletonUniversity 2007

8 A. Desrochers, "Island Network Analysis: MSTs and Dominating Sets" Dept. of Mathematics, Saint Michael's College, Winooski Park Colchester 2004

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

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

11 I. J. Dejter, "Efficient Dominating Sets in Cayley Graphs" 129 (129): 319-328, 2003

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

13 A. Schumacher, "Dominating-set-based Routing in AdHoc Networks"

14 "Dominating Set"

15 Y. Li, "Connected Dominating Sets in Wireless Networks"

16 M. Garey, "Computers and Intractability: A Guide to the Theory of NP-Completeness" W. H. Freeman 1979

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

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

19 F. Grandoni, "A Note on the Complexity of Minimum Dominating Set" 4 (4): 209-214, 2006

20 S. Butenko, "A New Heuristic for the Minimum Connected Dominating Set Problem on Ad Hoc Wireless Networks, In Recent Developments in Cooperative Control and Optimization" Kluwer Academic Publishers 61-73, 2003

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

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