Clique-connecting forest and stable set polytopes

Issue		RAIRO Oper. Res. Volume 44, Number 1, January-March 2010


Page(s)		73 - 83
DOI		10.1051/ro/2010005
Published online		08 February 2010

RAIRO-Oper. Res. 44 (2010) 73-83

Clique-connecting forest and stable set polytopes

Denis Cornaz

LIMOS, Complexe scientifique des Cézeaux, 63177 Aubiere Cedex, France; cornaz@isima.fr

Abstract

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.

Mathematics Subject Classification: 05C15 / 90C09

Key words: Graph / polytope / separation / facet

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.