Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
The hidden matching-structure of the composition of strips
du groupe GT Graphes et Applications

Date 2010-03-26  14:00-15:00
TitreThe hidden matching-structure of the composition of strips 
Résumé Composition of strips was introduced by Chudnovsky and Seymour as a key tool for decomposing claw-free graphs. In this talk we are going to reveal the close connection between the stable set problem in composed graphs and the matching theory. We will basically show that anything we can do for the strips, we can extend to composition of strips i.e. polytime algorithm (resp. separation, polyhedral description) for the strip extends to polytime algorithm (resp. separation, polyhedral description) for the composed graph. We will then apply those general results back to where they originated from: stable set in claw-free graphs, to show that the stable set polytope can be reduced to understanding the polytope in very basic structures (for most of which it is already known). In particular for a general claw-free graph $G$, we show an integral extended formulation for $STAB(G)$ and a procedure to separate in polynomial time over $STAB(G)$; moreover, we provide a complete characterization of $STAB(G)$ when $G$ is any claw-free graph with stability number at least 4 having neither homogeneous pairs nor 1-joins.  
LieuSalle 178 
OrateurGautier Stauffer 



Aucun document lié à cet événement.

Retour
Retour à l'index