Séminaire REGALRSS

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

08/03/2007
Intervenant(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
Carte du site