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.