TY - GEN
T1 - Tighter approximation bounds for minimum CDS in wireless ad hoc networks
AU - Li, Minming
AU - Wan, Peng Jun
AU - Yao, Frances
PY - 2009
Y1 - 2009
N2 - Connected dominating set (CDS) has a wide range of applications in wireless ad hoc networks. A number of approximation algorithms for constructing a small CDS in wireless ad hoc networks 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 . 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.
AB - Connected dominating set (CDS) has a wide range of applications in wireless ad hoc networks. A number of approximation algorithms for constructing a small CDS in wireless ad hoc networks 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 . 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.
UR - https://www.scopus.com/pages/publications/75649096025
U2 - 10.1007/978-3-642-10631-6_71
DO - 10.1007/978-3-642-10631-6_71
M3 - 会议稿件
AN - SCOPUS:75649096025
SN - 3642106307
SN - 9783642106309
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 699
EP - 709
BT - Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings
T2 - 20th International Symposium on Algorithms and Computation, ISAAC 2009
Y2 - 16 December 2009 through 18 December 2009
ER -