(6+∈)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs

摘要

It was a long-standing open problem whether the minimum weight dominating set in unit disk graphs has a polynomial-time constant-approximation. In 2006, Ambiihl et al solved this problem by presenting a 72approximation for the minimum weight dominating set and also a 89-approximation for the minimum weight connected dominating set in unit disk graphs. In this paper, we improve their results by giving a (6 + ∈)approximation for the minimum weight dominating set and a (10 + ∈)-approximation for the minimum weight connected dominating set in unit disk graphs where ∈ is any small positive number.