Skip to Main content Skip to Navigation
Conference papers

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

Résumé : 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.
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download

https://hal.inria.fr/inria-00176943
Contributor : David Coudert <>
Submitted on : Friday, October 5, 2007 - 12:11:39 AM
Last modification on : Friday, February 12, 2021 - 9:08:16 AM
Long-term archiving on: : Thursday, September 27, 2012 - 1:15:23 PM

File

16-Algotel07.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : inria-00176943, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

159

Files downloads

134