Independent set

From Glossary

Jump to: navigation, search


Given a graph, LaTeX: G=(V,E), an independent set (also called a stable set) is a subgraph induced by a subset of vertices, LaTeX: S, plus all edges with both endpoints in LaTeX: S, such that no two nodes in the subgraph are adjacent. A maximal independent set is one such that adding any node causes the subgraph to violate independence -- the added node is adjacent to some node already in the set. Given weights, LaTeX: w(v) for LaTeX: v \in V, the weight of an independent set, LaTeX: S, is the sum of the weights in LaTeX: S. The maximum independent set problem is to find an independent set of maximum weight. This is equivalent to finding a minimum weight vertex cover, say LaTeX: C, since LaTeX: V\backslash C is an independent set. (One can also refer to an independent set of arcs (or edges) as a subgraph with no two arcs (or edges) adjacent.)


Views
Personal tools