Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
Probabilistic Analysis of Rule 2
ArXiv.org
31 Aug 2004
Abstract
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.
Metrics
10 Record Views
Details
- Title
- Probabilistic Analysis of Rule 2
- Creators
- Jennie C HansenEric SchmutzLi Sheng
- Publication Details
- ArXiv.org
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Mathematics
- Other Identifier
- 991021863970404721