É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
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.
Type de document :
Communication dans un congrès
9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.95-99, 2007
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00176943
Contributeur : David Coudert <>
Soumis le : vendredi 5 octobre 2007 - 00:11:39
Dernière modification le : jeudi 11 janvier 2018 - 06:20:23
Document(s) archivé(s) le : jeudi 27 septembre 2012 - 13:15:23

Fichier

16-Algotel07.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00176943, version 1

Collections

ALGOTEL2007 | IBISC

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, 2007. 〈inria-00176943〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

131

Téléchargements de fichiers

109

Contact


archive-ouverte@inria.fr