|
Description:
|
We propose a novel branch -and -price (B &P ) approach to solve the maximum weighted independent set problem (MWISP ) . Our approach uses clones of vertices to create edge -disjoint partitions from vertex -disjoint partitions . We solve the MWISP on sub -problems based on these edge -disjoint partitions using a B &P framework , which coordinates sub -problem solutions by involving an equivalence relationship between a vertex and each of its clones . We present test results for standard instances and randomly generated graphs for comparison . We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly . |