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

doi:10.1007/s10878-007-9124-y

CSpace > 应用数学研究所

	On minimum m-connected k-dominating set problem in unit disc graphs
	Shang, Weiping 1,2; Yao, Frances 2; Wan, Pengjun 3; Hu, Xiaodong1
	2008-08-01
发表期刊	JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN	1382-6905
卷号	16 期号:2 页码:99-106
摘要	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.
关键词	k-dominating set m-connectivity unit disc graph approximation algorithm wireless sensor networks
DOI	10.1007/s10878-007-9124-y
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Interdisciplinary Applications ; Mathematics, Applied
WOS记录号	WOS:000256777800002
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/6633
专题	应用数学研究所
通讯作者	Hu, Xiaodong
作者单位	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
推荐引用方式 GB/T 7714	Shang, Weiping,Yao, Frances,Wan, Pengjun,et al. On minimum m-connected k-dominating set problem in unit disc graphs[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,2008,16(2):99-106.
APA	Shang, Weiping,Yao, Frances,Wan, Pengjun,&Hu, Xiaodong.(2008).On minimum m-connected k-dominating set problem in unit disc graphs.JOURNAL OF COMBINATORIAL OPTIMIZATION,16(2),99-106.
MLA	Shang, Weiping,et al."On minimum m-connected k-dominating set problem in unit disc graphs".JOURNAL OF COMBINATORIAL OPTIMIZATION 16.2(2008):99-106.