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

文献类型：期刊论文

作者Shang, Weiping1,2; Yao, Frances2; Wan, Pengjun3; 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
DOI10.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
语种英语
WOS记录号WOS:000256777800002
出版者SPRINGER
源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.

入库方式： OAI收割

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

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

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