Comparison of Two CDS Algorithms on Random Unit Ball Graphs.
Jennie C. Hansen, Eric Schmutz · 2005
This paper compares asymptotic “average case”performance of two closely related algorithms for finding small connected dominating sets. The stochastic model is that instances are random unit ball graphs formed from n random points in an ℓn × ℓn × ℓn cube. The first algorithm, widely known as “Rule 1”, is proved to be ineffective asymptotically: if ℓn = O ( 3 � n), then with asymptotic probability one Rule 1 selects a log n dominating set that consists of all but o(n) nodes in the network. In contrast, the expected size of Dai Li and Wu’s Rule 4 dominating set is Θ(ℓ 3 n). This latter performance is optimal insofar as the minimum connected dominating set also has Θ(ℓ 3 n) vertices ’on average’. These conclusions are three dimensional analogues of the two dimensional results in [18] and [19].