On minimum m-connected k-dominating set problem in unit disc graphs

被引：38

作者：

Shang, Weiping ^{[1
,2
]}

Yao, Frances ^{[2
]}

Wan, Pengjun ^{[3
]}

Hu, Xiaodong ^{[1
]}

机构：

[1] Chinese Acad Sci, Inst Appl Math, Beijing, Peoples R China

[2] City Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China

[3] IIT, Dept Comp Sci, Chicago, IL 60616 USA

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2008年 / 16卷 / 02期

关键词：

k-dominating set; m-connectivity; unit disc graph; approximation algorithm; wireless sensor networks;

D O I：

10.1007/s10878-007-9124-y

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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 subset S subset of 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.

引用

页码：99 / 106

页数：8