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.
Type de document :
Rapport
[Rapport de recherche] RR-3587, INRIA. 1998
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00073093
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 11:51:12
Dernière modification le : jeudi 11 janvier 2018 - 06:20:09
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:33:50

Fichiers

Identifiants

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

Partager

Métriques

Consultations de la notice

259

Téléchargements de fichiers

976