
arXiv: 1902.03548
A subset $S$ of nodes in a graph $G$ is a $k$-connected $m$-dominating set ($(k,m)$-cds) if the subgraph $G[S]$ induced by $S$ is $k$-connected and every $v \in V \setminus S$ has at least $m$ neighbors in $S$. In the $k$-Connected $m$-Dominating Set ($(k,m)$-CDS) problem the goal is to find a minimum weight $(k,m)$-cds in a node-weighted graph. For $m \geq k$ we obtain the following approximation ratios. For general graphs our ratio $O(k \ln n)$ improves the previous best ratio $O(k^2 \ln n)$ and matches the best known ratio for unit weights. For unit disc graphs we improve the ratio $O(k \ln k)$ to $\min\left\{\frac{m}{m-k},k^{2/3}\right\} \cdot O(\ln^2 k)$ -- this is the first sublinear ratio for the problem, and the first polylogarithmic ratio $O(\ln^2 k)/��$ when $m \geq (1+��)k$; furthermore, we obtain ratio $\min\left\{\frac{m}{m-k},\sqrt{k}\right\} \cdot O(\ln^2 k)$ for uniform weights. These results are obtained by showing the same ratios for the Subset $k$-Connectivity problem when the set $T$ of terminals is an $m$-dominating set with $m \geq k$.
FOS: Computer and information sciences, Connectivity, \(k\)-connected graph, subset \(k\)-connectivity, Analysis of algorithms and problem complexity, Approximation algorithms, 004, subset k-connectivity, \(m\)-dominating set, k-connected graph, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), rooted subset k-connectivity, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, m-dominating set, Data Structures and Algorithms (cs.DS), approximation algorithms, approximation algorithm, ddc: ddc:004
FOS: Computer and information sciences, Connectivity, \(k\)-connected graph, subset \(k\)-connectivity, Analysis of algorithms and problem complexity, Approximation algorithms, 004, subset k-connectivity, \(m\)-dominating set, k-connected graph, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), rooted subset k-connectivity, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, m-dominating set, Data Structures and Algorithms (cs.DS), approximation algorithms, approximation algorithm, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
