### 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^{2}) time algorithm using O(n^{2}) 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 | |

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

*Information Processing Letters*,

*43*(5), 229-235. https://doi.org/10.1016/0020-0190(92)90216-I

}

*Information Processing Letters*, vol. 43, no. 5, pp. 229-235. https://doi.org/10.1016/0020-0190(92)90216-I

**An efficient algorithm for finding a maximum weight 2-independent set on interval graphs.** / Hsiao, Ju Yuan; Tang, Chuan Yi; Chang, Ruay Shiung.

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 -