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  2007, with author Ventura P., in the category IASI Research Reports (or show them all):

---

IASI Research Report n. 663  (Previous )  

Anna Galluccio, Claudio Gentile, Paolo Ventura

On the stable set polytope of claw-free graphs

ABSTRACT

We define the class of geared (fuzzy) line graphs as the family of graphs obtained by repeated applications of the gear composition to a (fuzzy) line graph H. Using the decomposition theorem for claw-free graphs of Chudnovsky and Seymour [2], we show that this class represents a large subclass of claw-free graphs having stability number greater than 3. We provide a complete linear description of the stable set polytope of geared (fuzzy) line graphs. This result gives the first positive answer to the longstanding open question of finding a defining linear system for the stable set polytope of claw-free graphs which are not quasi-line [10]. Furthermore, it opens the possibility of designing a polyhedral algorithm for solving the stable set problem in claw-free graphs, possibly computationally more effective than the existing ones of complexity O(n6). Key words: stable set polytope, graph composition, claw-free graphs.