@article{997aec7734694d12ba8a246981d57643, title = "On minimum m-connected k-dominating set problem in unit disc graphs", abstract = "Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a S ⊆ V of minimal size such that every vertex in V\S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m ≤ 2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. {\textcopyright} 2007 Springer Science+Business Media, LLC.", keywords = "Approximation algorithm, k-dominating set, m-connectivity, Unit disc graph, Wireless sensor networks", author = "Weiping Shang and Frances Yao and Pengjun Wan and Xiaodong Hu", year = "2008", month = aug, doi = "10.1007/s10878-007-9124-y", language = "English", volume = "16", pages = "99--106", journal = "Journal of Combinatorial Optimization", issn = "1382-6905", publisher = "Springer New York LLC", number = "2", }