
























We develop deterministic approximation algorithms for the minimum dominating set problem in the CONGEST model with an almost optimal approximation guarantee. For $ε>1/{\text{poly}}\log Δ$ we obtain two algorithms with approximation factor $(1+ε)(1+\ln (Δ+1))$ and with runtimes $2^{O(\sqrt{\log n \log\log n})}$ and $O(Δ\cdot\text{poly}\log Δ+\text{poly}\log Δ\log^{*} n)$, respectively. Further we show how dominating set approximations can be deterministically transformed into a connected dominating set in the \CONGEST model while only increasing the approximation guarantee by a constant factor. This results in a deterministic $O(\log Δ)$-approximation algorithm for the minimum connected dominating set with time complexity $2^{O(\sqrt{\log n \log\log n})}$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。