跳到主要內容

臺灣博碩士論文加值系統

(34.204.180.223) 您好!臺灣時間:2021/08/05 23:56
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:蔣岳翰
研究生(外文):Yue-Han Chiang
論文名稱:最小連通支配集之演算法實作
論文名稱(外文):An Implementation of Algorithms for the Minimum Connected Dominating Set Problem
指導教授:張貿翔張貿翔引用關係吳邦一
指導教授(外文):Maw-Shang ChangBang-Ye Wu
口試委員:張貿翔吳邦一黃耀廷賴泳伶
口試委員(外文):Maw-Shang ChangBang-Ye WuYao-Ting HuangYung-Ling Lai
口試日期:2012-07-20
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:36
中文關鍵詞:連通支配集
外文關鍵詞:connected dominating set
相關次數:
  • 被引用被引用:0
  • 點閱點閱:203
  • 評分評分:
  • 下載下載:17
  • 收藏至我的研究室書目清單書目收藏:0
一個支配集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
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top