Greedy Algorithms for Minimum Connected Dominating Set Problems

De-Ren Yang ； Xiao-Feng Wang

《管理科學與統計決策》 7卷1期 (2010/03) Pp. 41-44

https://doi.org/10.6704/JMSSD.2010.7.1.41

並列摘要

To solve connected dominating problem, it is necessary to find minimum connected dominating set (MCDS for short). However, to find MCDS is NP-hardness. So, a graph model called interval graph is constructed from nodes of related network. Two greedy algorithms with linear (or polynomial time) are used to find MCDS on proper interval graph (or interval graph), and have I approximation ratio on the graphs. And spanning trees are constructed and used to validate the correctness and effectiveness of corresponding algorithms.

並列關鍵字

CDS ； MCDS ； interval graphs ； greedy algorithm ； spanning tree

參考文獻

Wan, P.,Alzoubi, K.,Frieder, O.(2002).Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks.Proc. of the IEEE Infocom.(Proc. of the IEEE Infocom).:

Gao, B. ,Yang, Y. ,Ma, H.(2005).A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks.International Journal of Communication.18(8),743-762.

Gandhi, P. ,Parthasarathy, S.(2007).Distributed algorithms for connected domination in wireless networks.Journal of Parallel and Distributed Computing.67(7),848-862.

Garey, M.,, D.(1979).Computers and Intractability: A Guide to The Theory of NP-completeness.San Fransisco:W. H. Freeman co..

Ruan, L.,Du, H.,Jia, X.(2004).A greedy approximation for minimum connected dominating sets.Theoretical Computer Science.329(1-3),325-330.