English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The problem of finding a minimum-weight connected dominating set (CDS) of agiven undirected graph has been studied actively, motivated by operations ofwireless ad hoc networks. In this paper, we formulate a new stochastic variantof the problem. In this problem, each node in the graph has a hidden randomstate, which represents whether the node is active or inactive, and we seek aCDS of the graph that consists of the active nodes. We consider an adaptivealgorithm for this problem, which repeat choosing nodes and observing thestates of the nodes around the chosen nodes until a CDS is found. Ouralgorithms have a theoretical performance guarantee that the sum of the weightsof the nodes chosen by the algorithm is at most $O(\alpha \log (1/\delta))$times that of any adaptive algorithm in expectation, where $\alpha$ is anapproximation factor for the node-weighted polymatroid Steiner tree problem and$\delta$ is the minimum probability of possible scenarios on the node states.

Adaptive Algorithm for Finding Connected Dominating Sets in Uncertain Graphs