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


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.


Talk 3 of the contributed session Fri.1.H 3012
"Cliques, stable sets, and perfect graphs" [...]
Cluster 2
"Combinatorial optimization" [...]


  Payday Loans In Indiana. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.