caa a22 4500 445805366 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00453-011-9512-7 doi (NATIONALLICENCE)springer-10.1007/s00453-011-9512-7 Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs [Elektronische Daten] [Minming Li, Peng-Jun Wan, Frances Yao] Connected dominating set (CDS) in unit disk graphs has a wide range of applications in wireless ad hoc networks. A number of approximation algorithms for constructing a small CDS in unit disk graphs have been proposed in the literature. The majority of these algorithms follow a general two-phased approach. The first phase constructs a dominating set, and the second phase selects additional nodes to interconnect the nodes in the dominating set. In the performance analyses of these two-phased algorithms, the relation between the independence number α and the connected domination number γ c of a unit-disk graph plays the key role. The best-known relation between them is $\alpha\leq3\frac{2}{3}\gamma_{c}+1$ . In this paper, we prove that α≤3.4306γ c +4.8185. This relation leads to tighter upper bounds on the approximation ratios of two approximation algorithms proposed in the literature. Springer Science+Business Media, LLC, 2011 Wireless ad hoc networks nationallicence Connected dominating set nationallicence Approximation algorithm nationallicence Geometric analysis nationallicence Li Minming Department of Computer Science, City University of Hong Kong, Hong Kong, Hong Kong SAR aut Wan Peng-Jun Department of Computer Science, Illinois Institute of Technology, Chicago, USA aut Yao Frances Department of Computer Science, City University of Hong Kong, Hong Kong, Hong Kong SAR aut Algorithmica Springer-Verlag 61/4(2011-12-01), 1000-1021 0178-4617 61:4<1000 2011 61 453 https://doi.org/10.1007/s00453-011-9512-7 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-011-9512-7 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Li Minming Department of Computer Science, City University of Hong Kong, Hong Kong, Hong Kong SAR aut NATIONALLICENCE 700 1- Wan Peng-Jun Department of Computer Science, Illinois Institute of Technology, Chicago, USA aut NATIONALLICENCE 700 1- Yao Frances Department of Computer Science, City University of Hong Kong, Hong Kong, Hong Kong SAR aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/4(2011-12-01), 1000-1021 0178-4617 61:4<1000 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer