Deterministic distributed construction of T-dominating sets in time T

DOI10.1016/J.DAM.2017.01.012zbMATH Open1396.05086arXiv1705.01229OpenAlexW2588377248MaRDI QIDQ1786883FDOQ1786883

Authors: Avery Miller, Andrzej Pelc 

Publication date: 25 September 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A $k$-dominating set is a set $D$ of nodes of a graph such that, for each node $v$, there exists a node $winD$ at distance at most $k$ from $v$. Our aim is the deterministic distributed construction of small $T$-dominating sets in time $T$ in networks modeled as undirected $n$-node graphs and under the $calLOCAL$ communication model. For any positive integer $T$, if $b$ is the size of a pairwise disjoint collection of balls of radii at least $T$ in a graph, then $b$ is an obvious lower 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/bightarrow1$) in time $T$. In the range of time $TinTheta(lo{g}^{\ast }n)$, the size of a $T$-dominating set turns out to be very sensitive to multiplicative constants in running time. Indeed, it follows from cite{KP}, that for time $T=gammalo{g}^{\ast }n$ with large constant $gamma$, it is possible to construct a $T$-dominating set whose size is a small fraction of $n$. By contrast, we show that, for time $T=alphalo{g}^{\ast }n$ for small constant $alpha$, the size of a $T$-dominating set must be a large fraction of $n$. Finally, when $Tino(lo{g}^{\ast }n)$, the above lower bound implies that, for any constant $x<1$, it is impossible to construct a $T$-dominating set of size smaller than $xn$, even on rings. On the positive side, we provide an algorithm that constructs a $T$-dominating set of size $n-Theta(T)$ on all graphs.

Full work available at URL: https://arxiv.org/abs/1705.01229

Recommendations

• An efficient distributed algorithm for constructing small dominating sets
• A distributed algorithm to find \(k\)-dominating sets
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• A distributed algorithm for minimum distance-\(k\) domination in trees
• A distributed algorithm for \(k\)-dominating sets

zbMATH Keywords

distributed algorithmundirected network\(\mathcal{LOCAL}\) model\(T\)-dominating set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)

Cites Work

• Distributed Computing: A Locality-Sensitive Approach
• Locality in Distributed Graph Algorithms
• \textsc{Maximal Independent Sets} in radio networks
• Combinatorial algorithms for distributed graph coloring
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Distributed Computing
• Leveraging Linial’s Locality Limit
• Constant-time distributed dominating set approximation
• Distributed approximation of capacitated dominating sets
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• An efficient distributed algorithm for constructing small dominating sets

This page was built for publication: Deterministic distributed construction of \(T\)-dominating sets in time \(T\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1786883)