Evènement pour le groupe GT Graphes et Applications


Date 2011-04-15  14:00-15:00
TitreSur la difficulté de séparer un graphe par des plus courts chemins 
Résumé Les schémas de routage et de calcul de distances les plus efficaces sont conçus à partir de décompositions hiéarchiques de la topologie en plus courts chemins. Ces constructions sont calculables efficacement pour de nombreuses topologies, comme les graphes planaires par exemple. Dans cet exposé je montrerais cependant que la décomposition d'une topologie arbitraire en k plus courts chemins est NP-difficile. 
LieuSalle 178 
OrateurEmilie DIOT 



Aucun document lié à cet événement.

Retour
Retour à l'index