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

Simple item page
dc.contributor.authorMasuda, Sumioen_US
dc.contributor.authorNakajima, K.en_US
dc.contributor.authorKashiwabara, Toshinobuen_US
dc.contributor.authorFujisawa, Toshioen_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T09:38:27Z
dc.date.available2007-05-23T09:38:27Z
dc.date.issued1987en_US
dc.description.abstractWe 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.en_US
dc.format.extent992450 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/4638
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1987-130en_US
dc.titleEfficient Enumeration of Maximal and Maximum Independent Sets of an Interval Graph and a Circular-Arc Graph.en_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR_87-130.pdf
Size:
969.19 KB
Format:
Adobe Portable Document Format
Download

Collections

Institute for Systems Research Technical Reports