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(n2 + β) 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*α).
All Science Journal Classification (ASJC) codes
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics