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 |
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)