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

---

IASI Research Report n. 563  (Next)  

Claudio Gentile, Giovanni Rinaldi, Haus U.-U., Koppe M., Weismantel R.

On the way to perfection: primal operations for stable sets in graphs

ABSTRACT

In this paper some operations are described that transform every graph into a perfect graph by replacing nodes with sets of new nodes. The transformation is done in such a way that every stable set in the perfect graph corresponds to a stable set in the original graph. These operations can be used in an augmentation procedure for finding a maximum weighted stable set in a graph. Starting with a stable set in a given graph one defines a simplex type tableau whose associated basic feasible solution is the incidence vector of the stable set. In an iterative fashion, nonbasic columns that would lead to pivoting into nonintegral basic feasible solutions, are replaced by new columns that one can read off from speciaal graph structures such as odd holes, odd antiholes, and various generalizations. Eventually, either a pivot leading to an integral basic feasible solution is performed, or the optimality of the current solution is proved.