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.
展开▼
机译：我们证明了边支配集问题的一般化，其中对于所有e∈E，每个边e都需要覆盖b e 次，对于一般的未加权图，它接受了线性时间2逼近，并且对于加权树可以最佳解决。我们展示了如何针对未加权树和其中所有e∈E的b e ∈{0,1}的加权树在线性时间内最佳求解。此外，我们表明它解决了树中加权匹配，顶点覆盖和边缘覆盖的一般化问题。
展开▼
