Key points are not available for this paper at this time.
Le célèbre théorème du max-flux min-coupe stipule qu'un nœud source s peut envoyer des informations à travers un réseau (V,E) vers un nœud de destination t à un débit de données déterminé par la min-coupe séparant s et t. Récemment, il a été montré que ce débit peut également être atteint pour le multicast vers plusieurs destinations à condition que les nœuds intermédiaires soient autorisés à réencoder les informations qu'ils reçoivent. En revanche, nous présentons des graphes où, sans codage, le débit doit être un facteur Ω(log|V|) plus petit. Cependant, jusqu'à présent, aucun algorithme rapide pour construire des schémas de codage appropriés n'était connu. Notre résultat principal est des algorithmes en temps polynomial pour construire des schémas de codage pour le multicast au débit de données maximal.
Sanders et al. (Sat,) ont étudié cette question.