Fast algorithms for generating all maximal independent sets of interval,circular-arc and chordal graphs

In this paper we give fast algorithms for generating all maximal independent sets of three special classes of graphs—interval, circular-arc, and chordal graphs. The worst-case running times of our algorithms are O(n² + β) for interval and circular-arc graphs, and $\text{O((n + e)}{}^1\text{α)}$ for chordal graphs, where n, e, and α are the numbers of vertexes, edges, and maximal independent sets of a graph, and β is the sum of the numbers of vertexes of all maximal independent sets. Our algorithms compare favorably with the fastest known algorithm for general graphs which has a worst-case running time of $\text{O(n}{}^1\text{e}{}^1\text{α)}$.