臺灣博碩士論文加值系統

(34.204.180.223) 您好！臺灣時間：2021/08/05 23:56

:::

詳目顯示

:

• 被引用: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 51.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Greedy Algorithms 82.1 Greedy Algorithm 1 . . . . . . . . . . . . . . . . . . . . . . . 82.2 Greedy Algorithm 2 . . . . . . . . . . . . . . . . . . . . . . . 112.3 Greedy Algorithm 3 . . . . . . . . . . . . . . . . . . . . . . . 133 Exact Algorithms 163.1 A Lower Bound of rc . . . . . . . . . . . . . . . . . . . . . . . 163.2 The Minimum Restricted Connected Dominating Set Problem 173.3 The Outline of Fomin et al.’s Algorithm . . . . . . . . . . . . 193.4 An Implementation of Fomin et al.’s Algorithm . . . . . . . . 233.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
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 最密k 集合問題在最大分支度三之圖上的正確解演算法 2 一些探測圖類別之辨識演算法設計 3 最大平衡子圖之演算法 4 基於強健連結以偵測社會網路上之真實朋友 5 在有號完全圖上尋找大的平衡子集之演算法 6 固定參數演算法與性質測試之研究 7 基於區域確定性的群集設計主動學習樣本資料挑選的方法 8 NUWeb 社群伺服器安裝與管理 9 電子商務搜尋引擎的設計與實作 10 影片轉漫畫:將動畫影片轉換為漫畫 11 藉由改變最少正負號以平衡完全圖 12 模擬社會網路生成的改進模型 13 基於鏈結與相似度對網路化資料分群的主動式學習 14 針對多核心軟體效能提升之資料溝通瓶頸分析 15 YouTube 影片分類統計瀏覽

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室