Approximation Algorithm for Minimum Weight (2, m )-Connected Dominating Set
IEEE Transactions on Networking · 2026 · 34 · 6245-6256
DOI: 10.1109/ton.2026.3712384 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Networking, 2026. Verfasst von Jiao Zhou und 4 weiteren Autor:innen. Die Arbeit nennt 50 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
Using a connected dominating set (CDS) as a virtual backbone of a wireless sensor network can effectively save energy, reduce interference, and extend network lifespan, which also has wide applications in geometric routing algorithms and network topology control. A fault-tolerant virtual backbone can be modeled as a $k$ -connected $m$ -dominating set (abbreviated as a $(k,m)$ -CDS) in a graph. In this paper, we present an approximation algorithm for the minimum weight $(2,m)$ -CDS problem in a general graph, which achieves approximation ratio at most $5.164H(n-1)$ , where $H(\gamma)=\sum _{i=1}^{\gamma }1/i$ is the $\gamma $ th Harmonic number and $n$ is the number of nodes in the graph. This ratio improves previously best known ratio by a factor of at least 3.87.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Zhou, J., Cai, Z., Huang, X., Zhang, Y., & Zhang, Z. (2026). Approximation Algorithm for Minimum Weight (2, m )-Connected Dominating Set. IEEE Transactions on Networking, 34, 6245-6256. https://doi.org/10.1109/ton.2026.3712384
Vancouver
Zhou J, Cai Z, Huang X, Zhang Y, Zhang Z. Approximation Algorithm for Minimum Weight (2, m )-Connected Dominating Set. IEEE Transactions on Networking. 2026;34:6245-6256. doi:10.1109/ton.2026.3712384
BibTeX
@article{Zhou2026,
author = {Zhou, Jiao and Cai, Zhipeng and Huang, Xiaohui and Zhang, Yaoyao and Zhang, Zhao},
title = {Approximation Algorithm for Minimum Weight (2, m )-Connected Dominating Set},
journal = {IEEE Transactions on Networking},
year = {2026},
volume = {34},
pages = {6245--6256},
doi = {10.1109/ton.2026.3712384}
}
EUVIMED