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 language | English |
|---|---|
| Pages (from-to) | 229-235 |
| Number of pages | 7 |
| Journal | Information Processing Letters |
| Volume | 43 |
| Issue number | 5 |
| DOIs | |
| 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
}
An efficient algorithm for finding a maximum weight 2-independent set on interval graphs. / Hsiao, Ju Yuan; Tang, Chuan Yi; Chang, Ruay Shiung.
In: Information Processing Letters, Vol. 43, No. 5, 05.10.1992, p. 229-235.Research output: Contribution to journal › Article
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 -