Issue |
RAIRO-Oper. Res.
Volume 41, Number 3, July-September 2007
Journées Polyèdres et Optimisation Combinatoire
|
|
---|---|---|
Page(s) | 289 - 294 | |
DOI | https://doi.org/10.1051/ro:2007022 | |
Published online | 21 August 2007 |
A note on the Chvátal-rank of clique family inequalities
1
Université de Bordeaux (LaBRI, INRIA), 351 cours de la Libération, 33405 Talence, France; pecher@labri.fr
2
Otto-von-Guericke-Universität Magdeburg,
Universitätsplatz 2, 39106 Magdeburg, Germany;
wagler@imo.math.uni-magdeburg.de
Received:
21
November
2006
Accepted:
21
December
2006
Clique family inequalities a∑v∈W xv + (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.
Mathematics Subject Classification: 05C69 / 90C10
Key words: Stable set polytope / Chvátal-rank
© EDP Sciences, ROADEF, SMAI, 2007
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.