Evènement pour le groupe
GT Graphes et Applications
Date | 2015-10-23 14:00-15:00 |
Titre | The N+-Perfect Graph Conjecture for Claw-Free Graphs |
Résumé | The subject of this talk is the study of the Lovasz-Schrijver PSD- operator N+ applied to the edge relaxation ESTAB(G) of the stable set polytope STAB(G) of a graph. We are particularly interested in the problem of characterizing the graphs G for which N+(G) := N+(ESTAB(G)) equals STAB(G), called N+-perfect graphs, and to find an appropriate polyhedral relaxation of STAB(G) that coincides with N+(G) and STAB(G) if and only if G is N+-perfect. An according conjecture has been recently formulated (N+-Perfect Graph Conjecture); we verify it for the well-studied class of claw-free graphs. |
Lieu | Salle 178 |
Orateur | Annegret Wagler |
Aucun document lié à cet événement.
RetourRetour à l'index