Probabilistic Analysis of Rule 2

Original · EN

Li and Wu proposed Rule 2, a localized approximation algorithm that attempts to find a small connected dominating set in a graph. Here we study the asymptotic performance of Rule 2 on random unit disk graphs formed from n random points in an sₙ by sₙ square region of the plane. If sₙ is below the threshold for connectivity, then Rule 2 produces a dominating set whose expected size is O(n/(loglog n)³/²). We conjecture that this bound is not optimal.