EUVIMEDEUVIMED entdecken
Crossref

Adaptive Algorithm for Stochastic Connected Dominating Set

Jiao Zhou, Zhao Zhang, Shaojie Tang

IEEE Transactions on Networking · 2026 · 34 · 933-940

DOI: 10.1109/ton.2025.3612409 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Networking, 2026. Verfasst von Jiao Zhou und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 48 Literaturangaben. Gefördert von: National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The problem of finding a minimum cardinality/weight connected dominating set (CDS) of a given graph has been studied extensively, because of its wide applications in wireless sensor networks (WSNs). Existing studies typically assume that the underlying network structure is fixed and preknown. However, given the inherent instability of mobile wireless devices, the network structure may be considered a random variable. Furthermore, determining the state of a node (active or inactive) often requires probing its local neighborhood. This motivates us to study the stochastic connected dominating set problem whose goal is to identify a connected dominating set within the graph comprised of active nodes while minimizing the probing cost. In this paper, we study the unweighted stochastic CDS problem, and present an $\left ({{\frac {1}{\delta }(H (\Delta -1)+1)+1}}\right)$ -approximation algorithm in expectation, where $H(\gamma)=\sum _{i=1}^{\gamma }1/i$ is the $\gamma $ th Harmonic number, $\Delta $ is the maximum degree of the graph, and $\delta $ is the minimum probability that a node is active.

Förderung

  • National Natural Science Foundation of China

Zitieren

APA

Zhou, J., Zhang, Z., & Tang, S. (2026). Adaptive Algorithm for Stochastic Connected Dominating Set. IEEE Transactions on Networking, 34, 933-940. https://doi.org/10.1109/ton.2025.3612409

Vancouver

Zhou J, Zhang Z, Tang S. Adaptive Algorithm for Stochastic Connected Dominating Set. IEEE Transactions on Networking. 2026;34:933-940. doi:10.1109/ton.2025.3612409

BibTeX
@article{Zhou2026,
  author = {Zhou, Jiao and Zhang, Zhao and Tang, Shaojie},
  title = {Adaptive Algorithm for Stochastic Connected Dominating Set},
  journal = {IEEE Transactions on Networking},
  year = {2026},
  volume = {34},
  pages = {933--940},
  doi = {10.1109/ton.2025.3612409}
}
Kostenlos starten →