A sequential algorithm for finding a maximum weightK-independent set on interval graphs

Abstract

In this paper an O(kn√logc+γ) time algorithm is presented to solve the maximum weight k-independent set problem on an interval graph with n vertices and non-negative integer weights, where c is the weight of the longest path of the interval graph and γ is the total size of all maximal cliques, given its interval representation. If the intervals are not sorted then considering the time for sorting the time complexity is of O(nlogn+kn √logc+γ). Using this algorithm the maximum weight 2-independent set problem for an interval graph with n vertices can be solved in O(n √logc + γ) time. The best known previous algorithm for 2-independent set problem requires O(n ²) time.