Given a weighted graph G = (V, E), each vertex v is associated with a weight w(v), the minimum weighted vertex cover (MWVC) problem is to choose a subset of vertices with minimum total weight such that every edge in the graph has at least one of its endpoints chosen. The neighborhood of a vertex v is denoted as N(u) = {u ∈ V|{u, u} ∈ E}. The weight of a vertex cover C, is defined as w(C) = Σ_(u∈C) w(u). Each edge e is associated with an edge weight w_e(e). We define the cost of a candidate solution C, denoted by cost(C) = Σ_(cover(e, C) = false) ω_e(e), which is the total weight of edges uncovered by C. For a vertex v, its score is denoted by score(v) = (cost(C) - cost(C'))/w(v), where C' = C{u} if u ∈ C, and C' = C ∪ {u} otherwise, which measures the benefit of changing the state of vertex u.
展开▼
