Efficient Enumeration of Maximal and Maximum Independent Sets of an Interval Graph and a Circular-Arc Graph.

View/ Open
Date
1987Author
Masuda, Sumio
Nakajima, K.
Kashiwabara, Toshinobu
Fujisawa, Toshio
Metadata
Show full item recordAbstract
We present efficient algorithms for generating all maximal and all maximum independent sets of an interval graph and a circular- arc graph. When an interval graph is given in the form of a family of n intervals, the first and second algorithms produce all maximal and all maximum independent sets, respectively, in O(n DOT log n+ (the size of an output)) time. When a circular- arc graph is given in the form of a family of n arcs on a circle, the third algorithm generates all maximal independent sets in O(n log n+ (the size of an output)) time. In the same situation, the fourth algorithm enumerates all maximum independent aets in O(n^2+ (the size of an output)) time. The first three algorithms are optimal to within a constant factor.