On the problem of finding all maximum weight independent sets in interval and circular-arc graphs

J.Y.-T. Leung (J. Algorithms, no.5, (1984)) presented algorithms for generating all the maximal independent sets in interval graphs and circular-arc graphs. The algorithms take O(n²+β) steps, where β is the sum of the number of nodes in all maximal independent sets. The authors use a new technique to give fast and efficient algorithms for finding all the maximum weight independent sets in interval graphs and circular-arc graphs. The algorithms take O(max(n ², β)) steps in O(n²) space, where β is the sum of the number of nodes in all maximum weight independent sets. The algorithms can be directly applied for finding a maximum weight independent set in these graphs in O(n²) steps. Thus, the result is an improvement over the best known result of O(n² log n) for finding the maximum weight independent set in circular-arc graphs