The expected size of the rule k dominating set

Jennie C. Hansen, Eric Schmutz, Li Sheng

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

Dai, Li, and Wu proposed Rule k, a localized approximation algorithm that attempts to find a small connected dominating set in a graph. In this paper we consider the "average-case" performance of two closely related versions of Rule k for the model of random unit disk graphs constructed from n random points in an ln × ln square. We show that if k = 3 and ln = o(vn), then for both versions of Rule k, the expected size of the Rule k dominating set is T(l n2) as n ? 8. It follows that, for ln in a suitable range, the expected size of the Rule k dominating sets are within a constant factor of the optimum. © Springer 2006.

Original languageEnglish
Pages (from-to)409-418
Number of pages10
JournalAlgorithmica
Volume46
Issue number3-4
DOIs
Publication statusPublished - Nov 2006

Keywords

  • Approximation algorithm
  • Dominating set
  • Localized algorithm
  • Performance analysis
  • Probabilistic analysis
  • Rule k
  • Unit disk graph

Fingerprint Dive into the research topics of 'The expected size of the rule k dominating set'. Together they form a unique fingerprint.

  • Cite this