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

[[abstract]]The paper introduces 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, the paper designs 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 the 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[[fileno]]2030209010078[[department]]資訊工程學