### 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 |

### Fingerprint

### Keywords

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

### Cite this

*Algorithmica*,

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

}

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

**The expected size of the rule k dominating set.** / Hansen, Jennie C.; Schmutz, Eric; Sheng, Li.

Research output: Contribution to journal › Article

TY - JOUR

T1 - The expected size of the rule k dominating set

AU - Hansen, Jennie C.

AU - Schmutz, Eric

AU - Sheng, Li

PY - 2006/11

Y1 - 2006/11

N2 - 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.

AB - 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.

KW - Approximation algorithm

KW - Dominating set

KW - Localized algorithm

KW - Performance analysis

KW - Probabilistic analysis

KW - Rule k

KW - Unit disk graph

UR - http://www.scopus.com/inward/record.url?scp=33846871921&partnerID=8YFLogxK

U2 - 10.1007/s00453-006-0104-x

DO - 10.1007/s00453-006-0104-x

M3 - Article

VL - 46

SP - 409

EP - 418

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 3-4

ER -