Clique-connecting forest and stable set polytopes
Cornaz, Denis (2010), Clique-connecting forest and stable set polytopes, RAIRO, 44, 1, p. 73-83. http://dx.doi.org/10.1051/ro/2010005
TypeArticle accepté pour publication ou publié
Edition Diffusion Presse Sciences
MetadataShow full item record
Abstract (EN)Let G=(V,E) be a simple undirected graph. A forest of G is said to be clique-connecting if each tree of F spans a clique of G. This paper adresses the clique-connecting forest polytope. First we give a formulation and a polynomial time separation algorithm. Then we show that the nontrivial nondegenerate facets of the stable set polytope are facets of the clique-connecting polytope. Finally we introduce a family of rank inequalities which are facets, and which generalize the clique inequalities.
Subjects / Keywordsfacet; separation; polytope; Graph
Showing items related by title and author.
Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié