Capacitated vertex covering with applications
Capacitated vertex covering with applications
复制标题
应用程序覆盖有能力的顶点
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Einat Or
中科院分区：
文献类型：
--
作者：
S. Guha;Refael Hassin;S. Khuller;Einat Or
本文研究了容量限制的顶点覆盖问题，它是众所周知的顶点覆盖问题的推广。给定一个图G =（V，E），顶点上有权值，目标是通过从顶点中选取最小权值的覆盖来覆盖所有边。当我们选择一个顶点的副本时，我们支付顶点的权重，并覆盖到这个顶点上的预定数量的边（它的容量）。这个问题是NP难的。我们给出了一个基于原始-对偶的2近似，并研究了几个推广，以及限制到树的问题。
In this paper we study the capacitated vertex cover problem, a generalization of the well known vertex cover problem. Given a graph G = (V, E) with weights on the vertices, the goal is to cover all the edges by picking a cover of minimum weight from the vertices. When we pick a copy of a vertex, we pay the weight of the vertex and cover upto a pre-specified number of edges incident on this vertex (its capacity). The problem is NP-hard. We give a primal-dual based 2 approximation and study several generalizations, as well as the problem restricted to trees.