Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00073038
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 11:40:37 AM
Last modification on : Thursday, February 11, 2021 - 2:48:04 PM
Long-term archiving on: : Sunday, April 4, 2010 - 11:32:04 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

273

Files downloads

228