The Expected Size of the Rule k Dominating Set |
| |
Authors: | Jennie C. Hansen Eric Schmutz Li Sheng |
| |
Affiliation: | (1) Actuarial Mathematics and Statistics Department, Herriot-Watt University, Edinburgh EH14 4AS, Scotland;(2) Department of Mathematics, Drexel University, Philadelphia, PA 19104, USA |
| |
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 square. We show that if and then for both versions of Rule k, the expected size of the Rule k dominating set is as It follows that, for in a suitable range, the expected size of the Rule k dominating sets are within a constant factor of the optimum. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|