09-36

On the Chvatal-rank of linear relaxations of the stable set polytope

by Holm, E.; Torres, L.M.; Wagler, A.

 

Preprint series: 09-36, Preprints

MSC:
90C27 Combinatorial optimization
52B99 None of the above but in this section
05C70 Factorization, matching, covering and packing

 

Abstract: We study the Chvatal-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 Chvatal-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).

Keywords: Chvatal-rank, stable sets, polyhedral combinatorics

Notes: To appear in: International Transactions in Operational Research


The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster