Vertex cover

From Glossary

Jump to: navigation, search

Given a graph, LaTeX: \textstyle G = \left [ V, E \right ], a vertex cover is a subset of LaTeX: V, say LaTeX: C, such that for each edge LaTeX: \textstyle (u,v) \in E, at least one of LaTeX: u and LaTeX: v is in LaTeX: C. Given weights, LaTeX: \{w(v)\} for LaTeX: v \in V, the weight of a vertex cover is the sum of weights of the nodes in LaTeX: 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.)

Personal tools