Maximum weight k-independent set problem on permutation graphs

Abstract

Based on a Directed Acyclic Graph approach, an O(kn ²) time sequential algorithm is presented to solve the maximum weight k-independent set problem on weighted-permutation graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph. This problem has many applications in practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design and routing problem.

Keywords:

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