Contributed Session Fri.1.H 3012

Friday, 10:30 - 12:00 h, Room: H 3012

Cluster 2: Combinatorial optimization [...]

Cliques, stable sets, and perfect graphs


Chair: Claudia Snels



Friday, 10:30 - 10:55 h, Room: H 3012, Talk 1

Maribel Jessica Montenegro
On the N-index of the stable set polytope related to antiwebs


In this work we investigate the application of the N and N+ operators, defined by Lovász and Schrijver (1990), to the edge relaxation of the stable set polytope related to antiwebs. The first immediate result is that these polytopes have N+-index equal to 1.
Moreover, we have proved that if an antiweb \overline{W}nk is such that n=qn'+1 and k=q(k'+1)-1 with n',k',q ∈ N and q ≥ 2, it contains a subantiweb which is isomorphic to the antiweb \overline{W}n'k' and the rank constraint of this subantiweb can be used to generate the rank constraint of \overline{W}nk. Using this construction we obtain upper-bounds on the N-index for some particular classes of antiwebs.



Friday, 11:30 - 11:55 h, Room: H 3012, Talk 3

Claudia Snels
Minimum weighted clique cover on strip-composed perfect graphs

Coauthors: Flavia Bonomo, Gianpaolo Oriolo


On a perfect graph G where a non negative weight function on the vertices w:V → R+ is given, the minimum weighted clique cover problem ({MWCC}), consists on finding a collection of cliques C, each one with a non-negative value yC, such that for every vertex v C ∈ C:v ∈ CyC ≥ w(v) and the weight C ∈ CyC is minimum.
The only available combinatorial algorithm for the {MWCC} in claw-free perfect graphs is due to Hsu and Nemhauser and dates back to 1984. More recently, Chudnovsky and Seymour in 2005 introduced a composition operation, strip-composition, in order to define their structural results for claw-free graphs; however, this composition operation is general and applies to non-claw-free graphs as well.
In this paper, we show that a {MWCC} of a perfect strip-composed graph, with the basic graphs belonging to a class G, can be found in polynomial time, provided that the {MWCC} problem can be solved on G in polynomial time. We also design a new, more efficient, combinatorial algorithm for the {MWCC} problem on strip-composed claw-free perfect graphs.


  personal loan . But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra In Canada influence on blood clots.