maximal independent set


Also found in: Acronyms, Wikipedia.

maximal independent set

[¦mak·sə·məl ‚in·də‚pen·dənt ′set]
(mathematics)
An independent set of vertices of a graph which is not a proper subset of another independent set.
References in periodicals archive ?
Recall that, by Theorem 3, the size of a maximal independent set is at least [square root of n + 1] - 1.
Note that the cardinality of any maximal independent set is smaller than or equal to the maximum independent set, so the result holds.
Huang, Minimum connected dominating sets and maximal independent sets in unit disk graphs, Theoretical Computer Science,
It is known that a maximum independent set of a graph on n vertices can be computed in O([1.4423.sup.n]) time by combining a result due to Moon and Moser, who showed in 1965 that the number of maximal independent sets of a graph is upper bounded by [3.sup.n/3] [32] (see also [30]), and a result due to Johnson, Yannakakis and Papadimitriou, providing in [27] a polynomial delay algorithm to generate all maximal independent sets.
They use the result due to Moon and Moser [32] as explained previously and an algorithm enumerating all the maximal independent sets to obtain an O([1.4423.sup.n]) time algorithm for MIDS.
Small maximal independent sets and faster exact graph coloring.
Generating all maximal independent sets: NP-hardness and polynomial-time algorithms.
Full browser ?