Efficient algorithms for interval graphs and circular‐arc graphs

U. I. Gupta, D. T. Lee, Joseph Leung

Research output: Contribution to journalArticlepeer-review

194 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)459-467
Number of pages9
JournalNetworks
Volume12
Issue number4
DOIs
StatePublished - Jan 1 1982

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this