Probabilistic Analysis of Rule 2
<|reference_start|>Probabilistic Analysis of Rule 2: 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_n by s_n square region of the plane. If s_n is below the threshold for connectivity, then Rule 2 produces a dominating set whose expected size is O(n/(loglog n)^{3/2}). We conjecture that this bound is not optimal.<|reference_end|>
@article{hansen2004probabilistic,
    title={Probabilistic Analysis of Rule 2},
    author={Jennie C. Hansen, Eric Schmutz, Li Sheng},
    journal={arXiv preprint arXiv:cs/0408068},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0408068},
    primaryClass={cs.DM}
}