Premium
Maximum independent sets of circular‐arc graphs: Simplified algorithm and proofs
Author(s) -
Zheng S. Q.
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199608)28:1<15::aid-net3>3.0.co;2-g
Subject(s) - mathematical proof , correctness , arc (geometry) , intersection (aeronautics) , mathematics , algorithm , independent set , combinatorics , hopcroft–karp algorithm , maximal independent set , simple (philosophy) , graph , discrete mathematics , chordal graph , 1 planar graph , geometry , philosophy , epistemology , engineering , aerospace engineering
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.