Evènement pour le groupe GT Graphes et Applications


Date 2007-10-05  14:00-15:00
TitreConnectivité dans les graphes planaires 
RésuméDans cet exposé je présenterai la variante d'un problème d'étiquetage: l'étiquetage avec ensembles interdits. Il s'agit de calculer des étiquettes pour les sommets d'un graphe G de sorte que l'on puisse déterminer ensuite si les sommets x et y sont dans la même composante connexe du graphes GX, étant données les étiquettes des sommets x,y et celles de l'ensemble interdits X. Pour les graphes planaires, je montrerai que l'on peut résoudre ce problème avec des étiquettes de O(log|V(G)|) bits. Travail joint avec: B. Courcelle, M. Kanté et A. Twigg  
LieuSalle 75 
OrateurCyril Gavoille 



Aucun document lié à cet événement.

Retour
Retour à l'index