Article ID: | iaor20101893 |
Volume: | 44 |
Issue: | 1 |
Start Page Number: | 73 |
End Page Number: | 83 |
Publication Date: | Jan 2010 |
Journal: | RAIRO Operations Research |
Authors: | Cornaz Denis |
Keywords: | cliques |
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.