G. Anastasi, A. Bartoli, and F. Spadoni, A reliable multicast protocol for distributed mobile systems: design and evaluation, IEEE Trans. Parallel Distributed Systems, vol.12, issue.10, pp.1009-1022, 2001.

G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-spaccamela et al., Complexity and Approximation, 1999.

M. Banikazemi, V. Moorthy, and D. K. Panda, Efficient collective communication on heterogeneous networks of workstations, Proceedings of the 27th International Conference on Parallel Processing (ICPP'98), 1998.

M. Banikazemi, J. Sampathkumar, S. Prabhu, D. K. Panda, and P. Sadayappan, Communication modeling of heterogeneous networks of workstations for performance characterization of collective operations, HCW'99, the 8th Heterogeneous Computing Workshop, pp.125-133, 1999.

O. Beaumont, A. Legrand, L. Marchal, and Y. Robert, Optimizing the steady-state throughput of broadcasts on heterogeneous platforms heterogeneous platforms, 2003.
URL : https://hal.archives-ouvertes.fr/inria-00071712

O. Beaumont, A. Legrand, L. Marchal, and Y. Robert, Pipelining broadcasts on heterogeneous platforms, International Parallel and Distributed Processing Symposium IPDPS, 2004.
URL : https://hal.archives-ouvertes.fr/inria-00358950

P. B. Bhat, C. S. Raghavendra, and V. K. Prasanna, Adaptive communication algorithms for distributed heterogeneous systems, Journal of Parallel and Distributed Computing, vol.59, issue.2, pp.252-279, 1999.

P. B. Bhat, C. S. Raghavendra, and V. K. Prasanna, Efficient collective communication in distributed heterogeneous systems, ICDCS'99 19th International Conference on Distributed Computing Systems, pp.15-24, 1999.

K. L. Calvert, M. B. Doar, and E. W. Zegura, Modeling internet topology, IEEE Communications Magazine, vol.35, issue.6, pp.160-163, 1997.

J. Cohen, P. Fraigniaud, J. C. König, and A. Raspaud, Optimized broadcasting and multicasting protocols in cut-through routed networks, IEEE Trans. Parallel Distributed Systems, vol.9, issue.8, pp.788-802, 1998.

, Synthesis of Parallel Algorithms, 1993.

M. R. Garey and D. S. Johnson, Computers and Intractability, a Guide to the Theory of NP-Completeness, 1991.

G. H. Golub and C. F. Van-loan, Matrix computations. Johns Hopkins, 1989.

T. Gopalsamy, M. Singhal, D. Panda, and P. Sadayappan, A reliable multicast algorithm for mobile ad hoc networks, ICDCS'02, 22nd Int. Conf. Distributed Computing Systems, pp.563-570, 2002.

N. G. Hall, W. Liu, and J. B. Sidney, Scheduling in broadcast networks, Networks, vol.32, issue.14, pp.233-253, 1998.

C. Hanen and A. Munier, Cyclic scheduling on parallel processors: an overview, Scheduling Theory and its Applications, pp.193-226, 1994.

J. Hatta and S. Shibusawa, Scheduling algorithms for efficient gather operations in distributed heterogeneous systems, 2000 International Conference on Parallel Processing, 2000.

R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, pp.85-103, 1972.

L. T. Kou, G. Markowsky, and L. Berman, A fast algorithm for steiner trees, Acta Informatica, vol.15, pp.141-145, 1981.

K. Kumar and J. Jaffe, Routing to multiple destinations in computer networks, IEEE Trans. Communications, vol.31, issue.3, pp.343-351, 1983.

A. Legrand, L. Marchal, and Y. Robert, Optimizing the steady-state throughput of scatter and reduce operations on heterogeneous platforms, 2003.
URL : https://hal.archives-ouvertes.fr/hal-00789447

A. Legrand, L. Marchal, and Y. Robert, Optimizing the steady-state throughput of scatter and reduce operations on heterogeneous platforms, APDCM'2004, 6th Workshop on Advances in Parallel and Distributed Computational Models, 2004.
URL : https://hal.archives-ouvertes.fr/hal-00789447

R. Libeskind-hadas, J. R. Hartline, P. Boothe, G. Rae, and J. Swisher, On multicast algorithms for heterogeneous networks of workstations, Journal of Parallel and Distributed Computing, vol.61, issue.11, pp.1665-1679, 2001.

X. Lin and L. M. Ni, Multicast communication in multicomputer networks, IEEE Trans. Parallel Distributed Systems, vol.4, issue.10, pp.1105-1117, 1993.

P. Liu, Broadcast scheduling optimization for heterogeneous cluster systems, Journal of Algorithms, vol.42, issue.1, pp.135-152, 2002.

P. Liu and T. Sheng, Broadcast scheduling optimization for heterogeneous cluster systems, SPAA'2000, 12th Annual ACM Symposium on Parallel Algorithms and Architectures, pp.129-136, 2000.

P. Liu and D. Wang, Reduction optimization in heterogeneous cluster environments, 14th International Parallel and Distributed Processing Symposium (IPDPS'2000), 2000.

B. Lowekamp and A. Beguelin, Eco: Efficient collective operations for communication on heterogeneous networks, 10th International Parallel and Distributed Processing Symposium (IPDPS'96), 1996.

F. Ooshita, S. Matsumae, and T. Masuzawa, Efficient gather operation in heterogeneous cluster systems, Proceedings of the 16th International Symposium on High Performance Computing Systems and Applications (HPCS'02), 2002.

S. Ramanathan, Multicast tree generation in networks with asymmetric links, IEEE/ ACM Transactions on Networking, vol.4, issue.4, pp.558-568, 1996.

D. F. Robinson, P. K. Mckinley, and B. H. Cheng, Optimal multicast communication in wormhole-routed torus networks, IEEE Trans. Parallel Distributed Systems, vol.6, issue.10, pp.1029-1042, 1995.

A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, vol.24, 2003.

A. Schrijver, Theory of Linear and Integer Programming, 1986.

R. Sivaram, R. Kesavan, D. K. Panda, and C. B. Stunkel, Architectural support for efficient multicasting in irregular networks, IEEE Trans. Parallel Distributed Systems, vol.12, issue.5, pp.489-513, 2001.

H. Takashami and A. Matsuyama, An approximate solution for the steiner tree problem in graphs, Intl. J. Math Educ. in Sci. and Technol, vol.14, issue.1, pp.15-23, 1983.

J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, Energy-aware wireless networking with directional antennas: the case of session-based broadcasting and multicasting, IEEE Trans. Mobile Computing, vol.1, issue.3, pp.176-191, 2002.

P. Winter, Steiner problem in networks: a survey, Networks, vol.17, issue.2, pp.129-167, 1987.

Y. Yang, J. Wang, and C. Qiao, Nonblocking WDM multicast switching networks, IEEE Trans. Parallel Distributed Systems, vol.11, issue.12, pp.1274-1287, 2000.

. Unité-de-recherche-inria-futurs, Parc Club Orsay Université -ZAC des Vignes 4, rue Jacques Monod -91893 ORSAY Cedex

. Unité-de-recherche-inria-lorraine, LORIA, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602