The expected size of the rule k dominating set

Jennie C. Hansen; Eric Schmutz; Li Sheng

doi:10.1007/s00453-006-0104-x

The expected size of the rule k dominating set

Jennie C. Hansen, Eric Schmutz, Li Sheng

Research output: Contribution to journal › Article › peer-review

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 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²) 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	https://doi.org/10.1007/s00453-006-0104-x
Publication status	Published - Nov 2006

Keywords

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

Access to Document

10.1007/s00453-006-0104-x

Cite this

@article{d09f9491da7b497a97d25252d2b4eb76,

title = "The expected size of the rule k dominating set",

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. {\textcopyright} Springer 2006.",

keywords = "Approximation algorithm, Dominating set, Localized algorithm, Performance analysis, Probabilistic analysis, Rule k, Unit disk graph",

author = "Hansen, {Jennie C.} and Eric Schmutz and Li Sheng",

year = "2006",

month = nov,

doi = "10.1007/s00453-006-0104-x",

language = "English",

volume = "46",

pages = "409--418",

journal = "Algorithmica ",

issn = "0178-4617",

publisher = "Springer",

number = "3-4",

}

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

SN - 0178-4617

VL - 46

SP - 409

EP - 418

JO - Algorithmica

JF - Algorithmica

IS - 3-4

ER -

The expected size of the rule k dominating set

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this