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

Séminaire REGALRSS

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


08.03.2007
Beteiligte : 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
Plan |