Efficient algorithms for interval graphs and circular‐arc graphs
Udaiprakash I. Gupta, D. T. Lee, Joseph Y.‐T. Leung · Networks · 1982
Abstract We show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in O(n log n) time [O(n) time if the endpoints of the intervals are sorted]. For the more general circular‐arc graphs, a maximum independent set and a minimum covering by disjoint completely connected sets or cliques can be found in O(n2) time, provided again that a corresponding family of arcs is given.