 License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-129392
URL:

### Approximating k-Connected m-Dominating Sets

 pdf-format:

### Abstract

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 ∈ V⧵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 ≥ k we obtain the following approximation ratios. For general graphs our ratio O(k ln n) improves the previous best ratio O(k² ln n) of [Z. Nutov, 2018] and matches the best known ratio for unit weights of [Z. Zhang et al., 2018]. For unit disk graphs we improve the ratio O(k ln k) of [Z. Nutov, 2018] to min{m/(m-k),k^{2/3}} ⋅ O(ln² k) - this is the first sublinear ratio for the problem, and the first polylogarithmic ratio O(ln² k)/ε when m ≥ (1+ε)k; furthermore, we obtain ratio min{m/(m-k), √k} ⋅ O(ln² k) for uniform weights. These results are obtained by showing the same ratios for the Subset k-Connectivity problem when the set of terminals is an m-dominating set.

### BibTeX - Entry

```@InProceedings{nutov:LIPIcs:2020:12939,
author =	{Zeev Nutov},
title =	{{Approximating k-Connected m-Dominating Sets}},
booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
pages =	{73:1--73:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-162-7},
ISSN =	{1868-8969},
year =	{2020},
volume =	{173},
editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 