On the Chvátal rank of linear relaxations of the stable set polytope

On the Chvátal rank of linear relaxations of the stable set polytope

0.00 Avg rating0 Votes
Article ID: iaor20107457
Volume: 17
Issue: 6
Start Page Number: 827
End Page Number: 849
Publication Date: Nov 2010
Journal: International Transactions in Operational Research
Authors: , ,
Abstract:

We study the Chvátal rank of two linear relaxations of the stable set polytope, the edge constraint and the clique constraint stable set polytope. For some classes of graphs whose stable set polytope is given by 0/1-valued constraints only, we present either the exact value of the Chvátal rank or upper bounds (of the order of their largest cliques and stable sets), which improve the bounds previously known from the literature (of the order of the graph itself).

Reviews

Required fields are marked *. Your email address will not be published.