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.


  . All this happens in case of bad medicines and wrong way of medication. Viagra Super Force is a treatment that has unique and surpassing formula combination.