Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs

Joseph Leung

Research output: Contribution to journalArticlepeer-review

35 Scopus citations

Abstract

In this paper we give fast algorithms for generating all maximal independent sets of three special classes of graphs-interval, circular-arc, and chordal graphs. The worst-case running times of our algorithms are O(n2 + β) for interval and circular-arc graphs, and O((n + e)*α) for chordal graphs, where n, e, and α are the numbers of vertexes, edges, and maximal independent sets of a graph, and β is the sum of the numbers of vertexes of all maximal independent sets. Our algorithms compare favorably with the fastest known algorithm for general graphs which has a worst-case running time of O(n*e*α).

Original languageEnglish (US)
Pages (from-to)22-35
Number of pages14
JournalJournal of Algorithms
Volume5
Issue number1
DOIs
StatePublished - Jan 1 1984

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs'. Together they form a unique fingerprint.

Cite this