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

Ju Yuan Hsiao, Chuan Yi Tang, Ruay Shiung Chang, An efficient algorithm for finding a maximum weight 2-independent set on interval graphs, Information Processing Letters, Volume 43, Issue 5, 1992, Pages 229-235, ISSN 0020-0190, https://doi.org/10.1016/0020-0190(92)90216-I. (https://www.sciencedirect.com/science/article/pii/002001909290216I) 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. Keywords: Analysis of algorithms; combinatorial problems; design of algorithms