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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A connected dominating set is a widely adopted model for the virtual backboneof a wireless sensor network. In this paper, we design an evolutionaryalgorithm for the minimum connected dominating set problem (MinCDS), whoseperformance is theoretically guaranteed in terms of both computation time andapproximation ratio. Given a connected graph $G=(V,E)$, a connected dominatingset (CDS) is a subset $C\subseteq V$ such that every vertex in $V\setminus C$has a neighbor in $C$, and the subgraph of $G$ induced by $C$ is connected. Thegoal of MinCDS is to find a CDS of $G$ with the minimum cardinality. We showthat our evolutionary algorithm can find a CDS in expected $O(n^3)$ time whichapproximates the optimal value within factor $(2+\ln\Delta)$, where $n$ and$\Delta$ are the number of vertices and the maximum degree of graph $G$,respectively.

Performance Guaranteed Evolutionary Algorithm for Minimum Connected Dominating Set