A sequential algorithm for finding a maximum weight K-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.

Keywords:

• Interval graph
• Independent set
• Network flow problem
• Combinatorial problems
• Design of algorithms
• Analysis of algorithms

C.R.Categories:

• E.1
• F.2
• G.2.2
• I.1.2.