EUVIMEDEUVIMED entdecken
Crossref

Approximation Algorithm for Minimum Weight (2, m )-Connected Dominating Set

Jiao Zhou, Zhipeng Cai, Xiaohui Huang, Yaoyao Zhang, Zhao Zhang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →