Construction d'arbres de diffusion multicast basée sur une modification de l'heuristique de Kruskal
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.
Loading...