TY - JOUR
T1 - On minimum m-connected k-dominating set problem in unit disc graphs
AU - Shang, Weiping
AU - Yao, Frances
AU - Wan, Pengjun
AU - Hu, Xiaodong
PY - 2008/8
Y1 - 2008/8
N2 - 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. © 2007 Springer Science+Business Media, LLC.
AB - 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. © 2007 Springer Science+Business Media, LLC.
KW - Approximation algorithm
KW - k-dominating set
KW - m-connectivity
KW - Unit disc graph
KW - Wireless sensor networks
UR - http://www.scopus.com/inward/record.url?scp=45849150749&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-45849150749&origin=recordpage
U2 - 10.1007/s10878-007-9124-y
DO - 10.1007/s10878-007-9124-y
M3 - 21_Publication in refereed journal
VL - 16
SP - 99
EP - 106
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
SN - 1382-6905
IS - 2
ER -