An efficient algorithm for finding a maximum weight 2-independent set on interval graphs

Ju Yuan Hsiao, Chuan Yi Tang, Ruay Shiung Chang

Research output: Contribution to journalArticle

62 Citations (Scopus)

Abstract

In this paper, we introduce an O(n) time algorithm to solve the maximum weight independent set problem on an interval graph with n vertices given its interval representation with sorted endpoints list. Based on this linear algorithm, we design an O(n2) time algorithm using O(n2) space to solve the maximum weight 2-independent set problem on an interval graph with n vertices. With a slight extension and modification of our algorithm, the maximum weight k-independent set problem on an interval graph with n vertices can be solved in O(nk) time using O(nk) space.

Original languageEnglish
Pages (from-to)229-235
Number of pages7
JournalInformation Processing Letters
Volume43
Issue number5
DOIs
Publication statusPublished - 1992 Oct 5

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this