License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.73
URN: urn:nbn:de:0030-drops-129392
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12939/
Go to the corresponding LIPIcs Volume Portal

Nutov, Zeev

Approximating k-Connected m-Dominating Sets

pdf-format:
LIPIcs-ESA-2020-73.pdf (0.6 MB)

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},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12939},
  URN =		{urn:nbn:de:0030-drops-129392},
  doi =		{10.4230/LIPIcs.ESA.2020.73},
  annote =	{Keywords: k-connected graph, m-dominating set, approximation algorithm, rooted subset k-connectivity, subset k-connectivity}
}

Keywords: k-connected graph, m-dominating set, approximation algorithm, rooted subset k-connectivity, subset k-connectivity
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI