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/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

A $k$-dominating set is a set $D$ of nodes of a graph such that, for eachnode $v$, there exists a node $w \in D$ at distance at most $k$ from $v$. Ouraim is the deterministic distributed construction of small $T$-dominating setsin time $T$ in networks modeled as undirected $n$-node graphs and under the$\cal{LOCAL}$ communication model.  For any positive integer $T$, if $b$ is the size of a pairwise disjointcollection of balls of radii at least $T$ in a graph, then $b$ is an obviouslower bound on the size of a $T$-dominating set. Our first result shows that,even on rings, it is impossible to construct a $T$-dominating set of size $s$asymptotically $b$ (i.e., such that $s/b \rightarrow 1$) in time $T$.  In the range of time $T \in \Theta (\log^* n)$, the size of a $T$-dominatingset turns out to be very sensitive to multiplicative constants in running time.Indeed, it follows from \cite{KP}, that for time $T=\gamma \log^* n$ with largeconstant $\gamma$, it is possible to construct a $T$-dominating set whose sizeis a small fraction of $n$. By contrast, we show that, for time $T=\alpha\log^* n $ for small constant $\alpha$, the size of a $T$-dominating set mustbe a large fraction of $n$.  Finally, when $T \in o (\log^* n)$, the above lower bound implies that, forany constant $x<1$, it is impossible to construct a $T$-dominating set of sizesmaller than $xn$, even on rings. On the positive side, we provide an algorithmthat constructs a $T$-dominating set of size $n- \Theta(T)$ on all graphs.

Deterministic Distributed Construction of $T$-Dominating Sets in Time $T$