Improved approximation bounds for edge dominating set in dense graphs

We analyze the simple greedy algorithm that iteratively removes the endpoints of a maximum-degree edge in a graph, where the degree of an edge is the sum of the degrees of its endpoints. This algorithm provides a 2-approximation to the minimum edge dominating set and minimum maximal matching problems. We refine its analysis and give an expression of the approximation ratio that is strictly less than 2 in the cases where the input graph has it vertices and at least epsilon (n 2) edges, for epsilon > 1/2. This ratio is shown to be asymptotically tight for epsilon > 1/2. (C) 2009 Elsevier B.V. All rights reserved.