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

doi:10.1007/s10878-007-9124-y

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 应用数学研究所

	On minimum m-connected k-dominating set problem in unit disc graphs
	Shang, Weiping 1,2; Yao, Frances 2; Wan, Pengjun 3; Hu, Xiaodong1
刊名	JOURNAL OF COMBINATORIAL OPTIMIZATION
	2008-08-01
卷号	16 期号:2 页码:99-106
关键词	k-dominating set m-connectivity unit disc graph approximation algorithm wireless sensor networks
ISSN号	1382-6905
DOI	10.1007/s10878-007-9124-y
英文摘要	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.
WOS研究方向	Computer Science ; Mathematics
语种	英语
出版者	SPRINGER
WOS记录号	WOS:000256777800002
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/6632]
专题	应用数学研究所
通讯作者	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.