An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph.

Loading...
Thumbnail Image

Files

TR_86-68.pdf (675.76 KB)
No. of downloads: 1313

Publication or External Link

Date

1986

Advisor

Citation

DRUM DOI

Abstract

A new algorithm is presented for finding a maximum independent set of a circular-arc graph. When the graph is given in the form of a family of n arcs, our algorithm requires only O(n log n) time and O(n) space. Furthermore, if the endpoints of the arcs are already sorted, it runs in O(n) time. This algorithm is time- and space-optimal to within a constant factor.

Notes

Rights