Construction d'arbres de diffusion multicast basée sur une modification de l'heuristique de Kruskal - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1998

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

Miklos Molnar

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.
Fichier principal
Vignette du fichier
RR-3587.pdf (277.35 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00073093 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00073093 , version 1

Citer

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⟩
216 Consultations
938 Téléchargements

Partager

Gmail Facebook X LinkedIn More