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 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications
Fingerprint Dive into the research topics of 'An efficient algorithm for finding a maximum weight 2-independent set on interval graphs'. Together they form a unique fingerprint.
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