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" [...]


  Do you need Missouri Loans Online as soon as possible? 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 No RX influence on blood clots.