.png){kind=icon}
.png){kind=icon}
Return
Adaptive Algorithm for Stochastic Connected Dominating Set
.png){kind=icon}
PRE
AI
DOI：10.1109/TON.2025.3612409.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 (1/delta (H(Delta - 1) + 1) + 1)-approximation algorithm in expectation, where H(gamma) = Sigma(gamma)(i=1) 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.
Keywords:
Stochastic combinatorial optimization
connected dominating set
adaptive algorithm
approximation ratio
Journal
I
IF:
0
Papers:
543
Citations:
0