Construction of 1- and 2-Connected k-Totally Dominating Set in Disk Graph

摘要：

In this paper we consider the minimum m-Connected A;Totally Dominating Set (m-k-CTDS) problem in disk graph. We present two centralized approximation algorithms for 1-k-CTDS and 2-k-CTDS problems with approximation ratios 1+In K/2(k-l) + K+K/k and 1+ln K/2(k-l) + K+3K/k, respectively, where K is 5 if k* = rmax/rmin = 1 , otherwise, K = 6(3|log2k*|+2).

关键词： minimnm m-connected k-totally dominating set maximum independent set disk graph wireless senor network

作者: Yefang Li Tianping Shuai Wenbao Ai

作者单位: School of Sciences Beijing University of Posts and Telecommunications Beijing, China

会议类型: 国际会议

会议名称: The Fourth International Joint Conference on Computational Science and Optimization(第四届计算科学与优化国际大会 CSO 2011)

会议地点: 昆明、丽江

会议语种:英文

页码: 1296-1299

在线出版日期: 2011-04-15（万方平台首次上网日期，不代表论文的发表时间）