最小連通支配集之演算法實作

一個支配集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.

並列關鍵字

connected dominating set

參考文獻

[1] F.V. Fomin, F. Grandoni and D. Kratsch, Solving Connected Dominating Set Faster than 2n, Algorithmica, 52 (2008), pp. 153–166

[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)

國際替代計量

最小連通支配集之演算法實作

未授權

主題瀏覽