|
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 NP-hard
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 almost-every-case 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 log|V|
vertices and achieves the performance ratio less than 1+\frac{3log|V|}{log|V|}. Thus in almost every-case, the algorithm finds in
polynomial time a solution that is extremely close to optimal.
|
