Probabilistic Analysis of Rule 2

Simple item page
dc.creatorHansen, Jennie C.
dc.creatorSchmutz, Eric
dc.creatorSheng, Li
dc.date2004-08-31
dc.date.accessioned2026-07-07T03:21:44Z
dc.date.available2026-07-07T03:21:44Z
dc.descriptionLi and Wu proposed Rule 2, a localized approximation algorithm that attempts to find a small connected dominating set in a graph. Here we study the asymptotic performance of Rule 2 on random unit disk graphs formed from n random points in an s_n by s_n square region of the plane. If s_n is below the threshold for connectivity, then Rule 2 produces a dominating set whose expected size is O(n/(loglog n)^{3/2}). We conjecture that this bound is not optimal.
dc.identifierhttps://arxiv.org/abs/cs/0408068
dc.identifierhttp://arxiv.org/abs/cs/0408068
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32316
dc.subjectDiscrete Mathematics
dc.titleProbabilistic Analysis of Rule 2
dc.typetext

Files

Collections

arXiv