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

Show full item record

Title: Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problem
Author: Sachdeva, Sandeep
Abstract: 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 .
URI: http : / /hdl .handle .net /1969 .1 /3251
Date: 2006-04-12

Citation

Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problem. Available electronically from http : / /hdl .handle .net /1969 .1 /3251 .

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show full item record

Search DSpace

Advanced Search

Browse