Évaluation en moyenne d'un algorithme pour la mise à jour d'un arbre de connexion

François Delbot (1) , Christian Laforest (1) , Nicolas Thibault (1)

1 IBISC - Informatique, Biologie Intégrative et Systèmes Complexes

Nous proposons un algorithme simple pour la mise à jour d'un arbre couvrant un groupe dont les membres peuvent arriver et/ou partir à chaque étape. L'objectif est alors de maintenir un arbre dont le diamètre est proche du diamètre minimum. La dynamicité des membres et le respect de la contrainte sur le diamètre peuvent nécessiter la reconstruction de l'arbre. Une étape de reconstruction étant coÛteuse, nous nous intéressons à la minimisation de ce nombre d'étapes. Si cette démarche a déjà été étudiée, les précédents travaux se sont restreints à l'étude du pire cas (algorithmes d'approximation ou étude du rapport de compétitivité dans le contexte online). Dans cet article, nous analysons le comportement de notre algorithme en moyenne. Pour cela, nous proposons quelques encadrements analytiques particuliers et un moyen algorithmique efficace pour calculer de manière exacte l'espérance du nombre de reconstructions (sous des hypothèses d'équiprobabilité). Nous donnons alors les grandes tendances de cette espérance.

Domaines: Algorithme et structure de données [cs.DS]; Réseaux et télécommunications [cs.NI]

François Delbot, Christian Laforest, Nicolas Thibault. Évaluation en moyenne d'un algorithme pour la mise à jour d'un arbre de connexion. 9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.95-99. ⟨inria-00176943⟩