Clique-connecting forest and stable set polytopes

Clique-connecting forest and stable set polytopes

0.00 Avg rating0 Votes
Article ID: iaor20101893
Volume: 44
Issue: 1
Start Page Number: 73
End Page Number: 83
Publication Date: Jan 2010
Journal: RAIRO Operations Research
Authors:
Keywords: cliques
Abstract:

Let G=(V,E) be a simple undirected graph. A forest F 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.

Reviews

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