A note on the Chvátal-rank of clique family inequalities

A note on the Chvátal-rank of clique family inequalities

0.00 Avg rating0 Votes
Article ID: iaor20083347
Country: France
Volume: 41
Issue: 3
Start Page Number: 289
End Page Number: 294
Publication Date: Jul 2007
Journal: RAIRO Operations Research
Authors: ,
Abstract:

Clique family inequalities a∑v∈W zv + (a−1)∑v∈W, xv≤aδ form an intriguing class of valid inequalities for the stable set polytopes of all graphs. We prove firstly that their Chvátal-rank is at most a, which provides an alternative proof for the validity of clique family inequalities, involving only standard rounding arguments. Secondly, we strengthen the upper bound further and discuss consequences regarding the Chvátal-rank of subclasses of claw-free graphs.

Reviews

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