Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs
S. Q. Zheng · Networks · 1996
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. © 1996 John Wiley & Sons, Inc.