臺灣博碩士論文加值系統

一個支配集S，是在一個無向簡單圖G = (V;E)，找一個V 的子集合S，使得V \S 裡的所有點，都至少與S 裡的一個點相鄰。而最小連通支配集問題，是找一個具有最小基數的支配集S，並且S 所形成的子圖G[S]是連通的。在這篇論文，我們以實作上的考量，稍微修改並實作於Solving Connected Dominating Set Faster than 2n(Fomin et al.(2008)) 內的確切解演算法，以觀察該演算法實際應用在最小連通支配集問題的效率。除以之外，我們也提出了三個啟發式演算法，並測試了具6 個不同密度的507 個隨機圖，以檢視他們的效率。

Let G = (V;E) be a simple undirected graph. A dominating set S in G is a subset of V such that each vertex in V \S is adjacent to some vertices in S. The minimum connected dominating set problem is to find a dominating set S of minimum cardinality such that G[S] is connected. It is known that the minimum connected dominating set problem is equivalent to the maximum leaf spanning tree problem. In this thesis, we slightly modify the exact algorithm given in the paper, Solving Connected Dominating Set Faster than 2n(Fomin et al.(2008)) mainly for implementation reasons and implement it to see whether the algorithm is practical in solving the minimum connected dominating set problem. Besides, we present three heuristics and run 507 random graphs with different densities to show their performance.

1 Introduction 5
1.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Greedy Algorithms 8
2.1 Greedy Algorithm 1 . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Greedy Algorithm 2 . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Greedy Algorithm 3 . . . . . . . . . . . . . . . . . . . . . . . 13
3 Exact Algorithms 16
3.1 A Lower Bound of rc . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 The Minimum Restricted Connected Dominating Set Problem 17
3.3 The Outline of Fomin et al.’s Algorithm . . . . . . . . . . . . 19
3.4 An Implementation of Fomin et al.’s Algorithm . . . . . . . . 23
3.5 Results of Our Implementation . . . . . . . . . . . . . . . . . 29

[1] F.V. Fomin, F. Grandoni and D. Kratsch, Solving Connected Dominating Set Faster than 2n, Algorithmica, 52 (2008), pp. 153–166
[2] A. Gupta, A. Kumar, T. Roughgarden, Simpler and better approximation algorithms for network design. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), pp. 365–372. ACM, New York (2003)
[3] C. Swamy, A. Kumar, Primal-dual algorithms for connected facility location problems. Algorithmica, 40 (2004), pp. 245–269
[4] Peng-Jun Wan, K.M. Alzoubi, O. Frieder, Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks, IEEE INFOCOM, 3 (2002), pp. 1597–1604
[5] F. Dai, J. Wu, An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 15 (2004), pp. 908–920
[6] M. Garey, D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., New York, USA, (1990)
[7] S. Guha, S. Khuller, Approximation algorithms for connected dominating sets. Algorithmica 20 (1998), pp 374–387
[8] F. Dorn, E. Penninkx, H. Bodlaender, F. Fomin.: Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions, in: Proceedings of the 13th Annual European Symposium on Algorithms (ESA), Springer, (2005), pp. 95–106
[9] R. Downey, M. Fellows, U. Stege.: Parameterized complexity: A framework for systematically confronting computational intractability, in: DIMACS Ser. Discrete Mathematics & Theoretical Computer Science, (1997), pp. 49–99
[10] H. Fernau, J. Kneis, D. Kratsch, A. Langer, M. Liedloff, D. Raible, P. Rossmanith, An exact algorithm for the maximum leaf spanning tree problem, in: Proceedings of the 4th International Workshop on Parameterized and Exact Computation IWPEC, (2009)
[11] Faisal N. Abu-Khzam, Amer E. Mouawada, Mathieu Liedloff.: An exact algorithm for connected red–blue dominating set. Journal of Discrete Algorithms, 9, (2011), pp. 252–262