This is the authors' abstract. We don't add key points for this paper.
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 ( n 2 ) time, provided again that a corresponding family of arcs is given.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Gupta et al. (1982) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: