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

Ju Yuan Hsiao; Chuan Yi Tang; Ruay Shiung Chang

doi:10.1016/0020-0190(92)90216-I

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

Ju Yuan Hsiao, Chuan Yi Tang, Ruay Shiung Chang

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article

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(n²) time algorithm using O(n²) 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(n^k) time using O(n^k) space.

Original language	English
Pages (from-to)	229-235
Number of pages	7
Journal	Information Processing Letters
Volume	43
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(92)90216-I
Publication status	Published - 1992 Oct 5

Fingerprint

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Cite this

Hsiao, J. Y., Tang, C. Y., & Chang, R. S. (1992). An efficient algorithm for finding a maximum weight 2-independent set on interval graphs. Information Processing Letters, 43(5), 229-235. https://doi.org/10.1016/0020-0190(92)90216-I

@article{67e263b4db314918bd2cf18bcba92f8c,

title = "An efficient algorithm for finding a maximum weight 2-independent set on interval graphs",

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.",

author = "Hsiao, {Ju Yuan} and Tang, {Chuan Yi} and Chang, {Ruay Shiung}",

year = "1992",

month = "10",

day = "5",

doi = "10.1016/0020-0190(92)90216-I",

language = "English",

volume = "43",

pages = "229--235",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

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

AU - Hsiao, Ju Yuan

AU - Tang, Chuan Yi

AU - Chang, Ruay Shiung

PY - 1992/10/5

Y1 - 1992/10/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0027112854&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027112854&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(92)90216-I

DO - 10.1016/0020-0190(92)90216-I

M3 - Article

AN - SCOPUS:0027112854

VL - 43

SP - 229

EP - 235

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 5

ER -

Access to Document

10.1016/0020-0190(92)90216-I