Probabilistic Analysis of Rule 2

Details Probabilistic Analysis of Rule 2 Probabilistic Analysis of Rule 2

2004-08-31

arxiv.org/abs/cs/0408068v1

Computer Science

Discrete Mathematics

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Probabilistic Analysis of Rule 2 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Probabilistic Analysis of Rule 2, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic Analysis of Rule 2 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-689189