中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 数学与系统科学研究院
  3. 中国科学院数学与系统科学研究院
  4. 应用数学研究所
Algorithms for minimum m-connected k-tuple dominating set problem

文献类型：期刊论文

作者Shang, Weiping; Wan, Pengjun; Yao, Frances; Hu, Xiaodong
刊名THEORETICAL COMPUTER SCIENCE
出版日期2007-08-22
卷号381期号:1-3页码:241-247
关键词connected dominating set approximation algorithm k-vertex connectivity wireless sensor networks
ISSN号0304-3975
DOI10.1016/j.tcs.2007.04.035
英文摘要In wireless sensor networks, a virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem and perform some other tasks such as area monitoring. Previous work in this area has mainly focused on how to set up a small virtual backbone for high efficiency, which is modelled as the minimum Connected Dominating Set (CDS) problem. In this paper we consider how to establish a small virtual backbone to balance efficiency and fault tolerance. This problem can be formalized as the minimum m-connected k-tuple dominating set problem, which is a general version of minimum CDS problem with m = 1 and k = 1. We propose three centralized algorithms with small approximation ratios for small m and improve the current best results for small k. (c) 2007 Elsevier B.V. All rights reserved.
WOS研究方向Computer Science
语种英语
WOS记录号WOS:000248966100019
出版者ELSEVIER SCIENCE BV
源URL[http://ir.amss.ac.cn/handle/2S8OKBNM/5059]  
专题应用数学研究所
通讯作者Shang, Weiping
作者单位1.Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, Beijing 10080, Peoples R China
2.IIT, Dept Comp Sci, Chicago, IL 60616 USA
3.City Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China
推荐引用方式
GB/T 7714		 Shang, Weiping,Wan, Pengjun,Yao, Frances,et al. Algorithms for minimum m-connected k-tuple dominating set problem[J]. THEORETICAL COMPUTER SCIENCE,2007,381(1-3):241-247.
APA Shang, Weiping,Wan, Pengjun,Yao, Frances,&Hu, Xiaodong.(2007).Algorithms for minimum m-connected k-tuple dominating set problem.THEORETICAL COMPUTER SCIENCE,381(1-3),241-247.
MLA Shang, Weiping,et al."Algorithms for minimum m-connected k-tuple dominating set problem".THEORETICAL COMPUTER SCIENCE 381.1-3(2007):241-247.

入库方式： OAI收割

来源：数学与系统科学研究院

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。