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

Given an undirected graph on a node set $V$ and positive integers $k$ and$m$, a $k$-connected $m$-dominating set ($(k,m)$-CDS) is defined as a subset$S$ of $V$ such that each node in $V \setminus S$ has at least $m$ neighbors in$S$, and a $k$-connected subgraph is induced by $S$. The weighted $(k,m)$-CDSproblem is to find a minimum weight $(k,m)$-CDS in a given node-weighted graph.The problem is called the unweighted $(k,m)$-CDS problem if the objective is tominimize the cardinality of a $(k,m)$-CDS. These problems have been activelystudied for unit disk graphs, motivated by the application of constructing avirtual backbone in a wireless ad hoc network. However, constant-approximationalgorithms are known only for $k \leq 3$ in the unweighted $(k,m)$-CDS problem,and for $(k,m)=(1,1)$ in the weighted $(k,m)$-CDS problem. In this paper, weconsider the case in which $m \geq k$, and we present a simple $O(5^kk!)$-approximation algorithm for the unweighted $(k,m)$-CDS problem, and aprimal-dual $O(k^2 \log k)$-approximation algorithm for the weighted$(k,m)$-CDS problem. Both algorithms achieve constant approximation factorswhen $k$ is a fixed constant.

Constant-approximation algorithms for highly connected multi-dominating sets in unit disk graphs