LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » Links » LIP6 events

Séminaire REGALRSS

Algorithmes pour la construction d'arbres couvrant des groupes dynamiques dans un graphe


03/08/2007
Speaker(s) : Nicola Thibault (IBISC)
Nous proposons des algorithmes pour la construction en ligne d'un arbre couvrant un groupe dynamique dans un graphe, où les sommets à ajouter et/ou retirer du groupe sont révélés au fur et à mesure. L'arbre doit alors être mis à jour, et respecter à chaque étape une certaine qualité évaluée en termes de distance maximum et/ou moyenne entre membres du groupe dans l'arbre. Nous donnons des bornes analytiques (inférieures et supérieures) pour différentes variantes de ce problème, et proposons, lorsque cela se révèle nécessaire, un principe de remise en cause maîtrisée de la solution courante.
 Mentions légales
Site map |