Abstract. The minimum connected dominating
set problem asks for a minimum size subset of vertices with the following
property: each vertex is required to be either in the subset, or adjacent
to some vertex in the subset, and the subgraph induced
by the subset is connected. This problem is known to be NPhard and, for any small ε
> 0, it cannot be solved by a polynomial time approximation algorithm
with the performance ratio less than (1  ε)ln V
for any graph G = (V, E) unless P = NP.
The present work deals with almosteverycase analysis of a simple
greedy algorithm for this problem. We show that for almost every graph
instance G = (V, E) of the problem, the greedy algorithm produces a connected
dominating set with at most logV vertices and achieves the performance ratio less than
1+\frac{3logV}{logV}. Thus in almost
everycase, the algorithm finds in polynomial time a solution that is
extremely close to optimal.
