Evènement pour le groupe
GT Graphes et Applications
| Date | 2007-06-08 14:00-15:00 |
| Titre | Sché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. |
| Lieu | Salle 75 |
| Orateur | Arnaud Labourel |
| Url | LaBRI |
Aucun document lié à cet événement.
RetourRetour à l'index