We present an algorithm that generates all maximal independent sets of a graph in
lexicographic order, with only polynomial delay between the output of two successive
independent sets. We also show that there is no polynomial-delay algorithm for generating
all maximal independent sets in reverse lexicographic order, unless P= NP.