1982/12/01 by U. I. Gupta, Udaiprakash I. Gupta, D. T. Lee +2 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory
paper · doi:10.1002/net.3230120410
crossref issued 1982/12/01 · crossref published 1982/12/01 · crossref published-print 1982/12/01 · openalex publication_date 1982/12/01 · crossref published-online 2006/10/11 · crossref created 2007/05/11 · crossref deposited 2023/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26 · crossref indexed 2026/08/01
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 ( n 2 ) time, provided again that a corresponding family of arcs is given.