✦ LIBER ✦

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

✍ Scribed by Zheng, S. Q.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 421 KB
Volume: 28
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199608)28:1<15::aid-net3>3.0.co;2-g

No coin nor oath required. For personal study only.

✦ Synopsis

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.