Maximal Independent Set

A maximal independent set is an independent set which is a maximal set, i.e., an independent set that is not a subset of any other independent set.

The generic term "maximal independent set" is unfortunately commonly used to refer to a maximal independent vertex set of a graph even though other types of maximal independent sets (in particular maximal independent edge sets) exist.

See also

Maximal Independent Edge Set, Maximal Independent Vertex Set

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Maximal Independent Set." From MathWorld--A Wolfram Web Resource.

Subject classifications