Construction of 1- and 2-Connected k-Totally Dominating Set in Disk Graph
Yefang Li, Tianping Shuai, Wenbao Ai · 2011
In this paper we consider the minimum m-Connected k-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+ln K/2(k-1)+K+K/k and 1+ln K/2(k-1)+K+3K/k, respectively, where K is 5 if k*=rmax/rmin=1, otherwise, K=6(3|log2k*|+2).