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 O((n + e)^*α) 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 O(n^*e^*α).