Evènement pour le groupe
GT Graphes et Applications
Date | 2011-04-15 14:00-15:00 |
Titre | Sur 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. |
Lieu | Salle 178 |
Orateur | Emilie DIOT |
Aucun document lié à cet événement.
RetourRetour à l'index