Evènement pour le groupe GT Graphes et Applications


Date 2007-06-08  14:00-15:00
TitreSchéma d'adjacence pour les graphes planaires 
RésuméUn schéma d'adjacence d'un graphe est un codage du graphe distribué sur ses sommets. Le principe est d'associer à chaque sommet du graphe de l'information sous la forme d'une étiquette binaire de façon à ce que l'on puisse déterminer l'adjacence entre deux sommets en examinant seulement leurs étiquettes. Je vous présenterais un tel schéma pour les graphes planaires de n sommets avec des étiquettes de (2+o(1))log n bits. L'idée du schéma est d'utiliser un nouveau schéma avec de étiquettes de (1+o(1))log n bits pour les planaires extérieurs et la décomposition des graphes planaires en deux graphes planaires extérieurs. De la même manière, on étend ce résultat aux graphes excluant un mineur fixé en utilisant un nouveau schéma pour les graphes d'arboricité bornée. 
LieuSalle 75 
OrateurArnaud Labourel 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index