An nO(1/ϵ) Approximation Scheme For The Minimum Dominating Set In Unit Disk Graphs
Jittat Fakcharoephol, Pattara Sukprasert · 2018
We present an nO(1/ε)PTAS for minimum dominating set problem in unit disk graphs. Our approach gives an asymptotic improvement over the best known [Nieberg and Hurink WAOA2005], which runs in nO(1/ε log 1/ε), under a more strict (but typical) assumption that the underlying geometric structure is known, i.e., the locations of all unit disks are specified. Our key ingredient is an improved dynamic programming algorithm that depends exponentially on a more essential 1-dimensional “width” of the problem.