Return to search

Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problem

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.

Identiferoai:union.ndltd.org:TEXASAandM/oai:repository.tamu.edu:1969.1/3251
Date12 April 2006
CreatorsSachdeva, Sandeep
ContributorsWilhelm, Wilbert E., Sen, Arun, Hicks, Illya
PublisherTexas A&M University
Source SetsTexas A and M University
Languageen_US
Detected LanguageEnglish
TypeElectronic Thesis, text
Format1749029 bytes, electronic, application/pdf, born digital

Page generated in 0.0018 seconds