The expected size of the rule k dominating set

Jennie C. Hansen, Eric Schmutz, Li Sheng

Research output: Contribution to journalArticle

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

Fingerprint

Dominating Set
Unit Disk Graph
Connected Dominating Set
Random Graphs
Approximation Algorithms
Graph in graph theory
Range of data

Keywords

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

Cite this

Hansen, Jennie C. ; Schmutz, Eric ; Sheng, Li. / The expected size of the rule k dominating set. In: Algorithmica . 2006 ; Vol. 46, No. 3-4. pp. 409-418.
@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. {\circledC} 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 = "11",
doi = "10.1007/s00453-006-0104-x",
language = "English",
volume = "46",
pages = "409--418",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer",
number = "3-4",

}

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

In: Algorithmica , Vol. 46, No. 3-4, 11.2006, p. 409-418.

Research output: Contribution to journalArticle

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 -