| 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
|