VERTEX COVER

Vertex cover - Given a graph , G=[V,E], a vertex cover is a subset of V, say C, such that for each edge (u,v) in E, at least one of u and v is in C. Given weights, (w(v)) for v in V, the weight of a vertex cover is the sum of weights of the nodes in C. The minimum weight vertex cover problem is to find a vertex cover whose weight is minimum. (Also see the covering problem and the maximum weight independent set problem.