Linear Time Algorithms for Generalized Edge Dominating Set Problems

We prove that a generalization of the edge dominating set problem, in which each edge e needs to be covered b _e times for all e∈E, admits a linear time 2-approximation for general unweighted graphs and that it can be solved optimally for weighted trees. We show how to solve it optimally in linear time for unweighted trees and for weighted trees in which b _e ∈{0,1} for all e∈E. Moreover, we show that it solves generalizations of weighted matching, vertex cover, and edge cover in trees.