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]  (see also ), and a result due to Johnson, Yannakakis and Papadimitriou, providing in  a polynomial delay algorithm to generate all maximal independent sets.
They use the result due to Moon and Moser  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.