| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [5 references]
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
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