Skip to Main content Skip to Navigation
Reports

Construction d'arbres de diffusion multicast basée sur une modification de l'heuristique de Kruskal

Miklos Molnar 1
1 MODEL - Modeling Random Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Résumé : La construction d'arbres couvrants partiels de poids minimum est un problème NP-complet pour lequel plusieurs heuristiques approximatives ont déjà été formulées. La plupart d'entre elles (telle l'heuristique de Kruskal) sont basées sur la recherche des plus courts chemins pour relier différentes composantes de l'arbre. Dans ce rapport, nous présentons un algorithme de construction d'une approximation de l'arbre minimum de Steiner (qui est l'arbre optimal d'une diffusion multicast) basé sur des structures plus avantageuses que celles des plus courts chemins. L'algorithme réalise les connexions sous forme des arbres minimum de Steiner limités en nombre de noeuds.
Document type :
Reports
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

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

Identifiers

  • HAL Id : inria-00073093, version 1

Citation

Miklos Molnar. Construction d'arbres de diffusion multicast basée sur une modification de l'heuristique de Kruskal. [Rapport de recherche] RR-3587, INRIA. 1998. ⟨inria-00073093⟩

Share

Metrics

Record views

342

Files downloads

1273