In the classical vertex cover problem, we are given a graph G = (V, E) and we aim to find a minimum cardinality cover of the edges, i.e. a subset of the vertices C {is contained in} V such that for every edge e ∈ E, at least one of its extremities belongs to C. In the MIN-POWER-COVER version of the vertex cover problem, we consider an edge-weighted graph and we aim to find a cover of the edges and a valuation (power) of the vertices of the cover minimizing the total power of the vertices. We say that an edge e is covered if at least one of its extremities has a valuation (power) greater than or equal than the weight of e. In this paper, we consider MIN-POWER-COVER variants of various classical problems, including vertex cover, min cut, spanning tree and path problems.
展开▼
