Publications of Paolo Ventura

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  2006, with author Ventura P., in the category IASI Research Reports (or show them all):


IASI Research Report n. 641    

Anna Galluccio, Claudio Gentile, Paolo Ventura

New facet defining inequalities for the Stable Set Polytope

ABSTRACT
We present a new graph composition, named {it gear composition}, that produces a graph $G$ by composing a given graph $H$ and a fixed graph $B$ called {it gear}. We study the polyhedral properties of this composition and provide sufficient conditions to generate facet defining inequalities for $STAB(G)$ starting from facet defining inequalities for $STAB(H)$. We also prove that the separation problem for these inequalities can be solved in polynomial time for some interesting cases. As a final remark, we show how to use the gear composition to build counterexamples to a conjecture on the facial structure of $STAB(G)$ when $G$ is claw-free and has stability number greater than three.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -