Arbre couvrant partiel pseudo-optimal pour diffusion multipoint

Raymond Marie 1 Miklos Molnar 1
1 MODEL - Modeling Random Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Résumé : Dans un réseau de communication, la diffusion multipoint des messages est optimale, du point de vue topologique, si le support de la diffusion correspond à un arbre couvrant partiel minimal. La construction d'arbres couvrants partiels minimaux (le problème de Steiner des réseaux) étant NP-complete, plusieurs heuristiques ne nécessitant qu'un temps polynomial d'exécution ont été formulées. Pour la diffusion multipoint des messages, la longueur de l'arbre utilisé est très importante puisque le coût de la diffusion dépend de cette longueur. Une partie des heuristiques (comme l'heuristique de Takahashi et de Matsuyama) utilise les plus courts chemins du graphe pour construire l'arbre. Dans ce rapport, nous donnons un algorithme de construction de l'arbre approché de l'arbre de Steiner minimal. Dans certains cas, notre algorithme permet de diminuer la longueur de l'arbre construit en temps polynomial. L'algorithme proposé utilise des structures plus avantageuses que les plus courts chemins et fait, si nécessaire, des connexions sous forme d'arbres de Steiner minimaux simples.
Type de document :
Rapport
[Rapport de recherche] RR-3636, INRIA. 1999
Liste complète des métadonnées

https://hal.inria.fr/inria-00073038
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 11:40:37
Dernière modification le : mercredi 11 avril 2018 - 02:00:45
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:32:04

Fichiers

Identifiants

  • HAL Id : inria-00073038, version 1

Citation

Raymond Marie, Miklos Molnar. Arbre couvrant partiel pseudo-optimal pour diffusion multipoint. [Rapport de recherche] RR-3636, INRIA. 1999. 〈inria-00073038〉

Partager

Métriques

Consultations de la notice

232

Téléchargements de fichiers

187