### 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 l_{n} × l_{n} square. We show that if k = 3 and l_{n} = o(vn), then for both versions of Rule k, the expected size of the Rule k dominating set is T(l _{n}^{2}) as n ? 8. It follows that, for l_{n} in a suitable range, the expected size of the Rule k dominating sets are within a constant factor of the optimum. © Springer 2006.

Original language | English |
---|---|

Pages (from-to) | 409-418 |

Number of pages | 10 |

Journal | Algorithmica |

Volume | 46 |

Issue number | 3-4 |

DOIs | |

Publication status | Published - 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

Hansen, J. C., Schmutz, E., & Sheng, L. (2006). The expected size of the rule k dominating set.

*Algorithmica*,*46*(3-4), 409-418. https://doi.org/10.1007/s00453-006-0104-x