J. Bermond, R. Klasing, N. Morales, and S. Perennes, Gathering traffic in radio networks, the grid and path cases, 2004.

I. Caragiannis, A. Ferreira, C. Kaklamanis, S. Pérennes, P. Persiano et al., Approximate Constrained Bipartite Edge Coloring, 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'01), pp.21-31, 2001.
DOI : 10.1007/3-540-45477-2_4
URL : https://hal.archives-ouvertes.fr/hal-00371101

I. Caragiannis, A. Ferreira, C. Kaklamanis, S. Pérennes, R. et al., Fractional Path Coloring with Applications to WDM Networks, Proc. of the 28th ICALP, pp.732-743, 2001.
DOI : 10.1007/3-540-48224-5_60

T. Erlebach, Maximum weight edge-disjoint paths in bidirected tree, Communication and Data Management in Large Networks. Workshop of INFORMATIK'99, pp.13-19, 1999.

T. Erlebach and K. Jansen, Maximizing the number of Connections in Optical Tree Networks, Proceedings of the Ninth Annual International Symposium on Algorithms and Computation (ISAAC'98), pp.179-188, 1998.
DOI : 10.1007/3-540-49381-6_20

T. Erlebach, K. Jansen, and E. Seidel, Polynomial-Time Approximation Schemes for Geometric Intersection Graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pp.1-671, 2001.
DOI : 10.1137/S0097539702402676

M. Flammini and S. Pérennes, Lower Bounds on systolic gossiping. Information and Computation
DOI : 10.1109/ipps.1997.580949
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.3925

L. Gasieniec and I. Potapov, Gossiping with Unit Messages in Known Radio Networks, Proceedings of the IFIP 17th World Computer Congress -TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science Kluwer, B.V, pp.193-205, 2002.
DOI : 10.1007/978-0-387-35608-2_17

M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, vol.2, issue.2, pp.169-197, 1981.
DOI : 10.1007/BF02579273

M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, second corrected ed, 1993.

B. Harry, H. I. Marathe, M. V. Radhakrishnan, V. Ravi, S. S. Rosenkrantz et al., NC-approximation schemes for NPand PSPACE-hard problems for geometric graphs, Journal of Algorithms, vol.26, issue.2, pp.238-274, 1998.

D. S. Hochbaum and W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM, vol.32, issue.1, pp.130-136, 1985.
DOI : 10.1145/2455.214106

J. Hromkovic, R. Klasing, D. Pardubská, and J. Waczulik, Effective Systolic Algorithms for Gossiping in Cycles, Parallel Processing Letters, vol.08, issue.02, pp.197-205, 1998.
DOI : 10.1142/S0129626498000213

J. Hromkovic, R. Klasing, D. Pardubská, W. Unger, and H. Wagener, The complexity of systolic dissemination of information in interconnection networks, R.A.I.R.O. Theoretical Informatics and Applications, vol.28, pp.3-4, 1994.

K. Jansen, Approximate strong separation with application in fractional graph coloring and preemptive scheduling, Theoretical Computer Science, vol.1, issue.3302, pp.239-256, 2003.

D. R. Kowalski and A. Pelc, Time of Deterministic Broadcasting in Radio Networks with Local Knowledge, SIAM Journal on Computing, vol.33, issue.4, pp.870-891, 2004.
DOI : 10.1137/S0097539702419339

V. Kumar, Approximating circular arc colouring and bandwidth allocation in all-optical ring networks, Proc. of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX'98), pp.147-158, 1998.
DOI : 10.1007/BFb0053971

C. Lund, Y. , and M. , On the hardness of approximating minimization problems, Journal of the ACM, vol.41, issue.5, pp.960-981, 1994.
DOI : 10.1145/185675.306789

A. Tucker, Coloring a Family of Circular Arcs, SIAM Journal on Applied Mathematics, vol.29, issue.3, pp.493-502, 1975.
DOI : 10.1137/0129040

. Unité-de-recherche-inria-sophia and . Antipolis, route des Lucioles -BP 93 -06902 Sophia Antipolis Cedex (France) Unité de recherche INRIA Futurs : Parc Club Orsay Université -ZAC des Vignes 4, 2004.

I. Unité-de-recherche and . Lorraine, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602 Villers-lès-Nancy Cedex (France) Unité de recherche INRIA Rennes : IRISA, Campus universitaire de Beaulieu -35042 Rennes Cedex (France) Unité de recherche INRIA Rhône-Alpes : 655, avenue de l'Europe -38334 Montbonnot Saint-Ismier (France) Unité de recherche INRIA Rocquencourt, Domaine de Voluceau -Rocquencourt -BP 105 -78153 Le Chesnay Cedex

I. De-voluceau-rocquencourt, BP 105 -78153 Le Chesnay Cedex (France) http://www.inria.fr ISSN, pp.249-6399