Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs

We present a simple optimal algorithm for the problem of finding maximum independent sets of circular-arc graphs. Given an intersection model S of a circular-arc graph G, our algorithm computes a maximum independent set of G in O(n) space and O(n) or O (n log n) time, depending on whether the endpoints of arcs in S are sorted or not. The proofs of the correctness and the complexities of the algorithm are straightforward, and the techniques used can be generalized to solve other problems on circular-arc graphs efficiently.