M. Bellare, O. Goldreich, and M. Sudan, Free bits, PCPs and non-approximability-towards tight results, Proceedings of IEEE 36th Annual Foundations of Computer Science, pp.804-915, 1998.
DOI : 10.1109/SFCS.1995.492573
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.6494

J. Bermond, R. Corrêa, and J. Yu, Gathering Algorithms on Paths Under Interference Constraints, 6th Conference on Algorithms and Complexity, 2006.
DOI : 10.1007/11758471_14
URL : https://hal.archives-ouvertes.fr/hal-00512286

J. Bermond, J. Galtier, R. Klasing, N. Morales, and S. Perennes, Gathering in specific radio networks, 8` emes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'06), Trégastel, 2006.
URL : https://hal.archives-ouvertes.fr/hal-00344620

J. Bermond, L. Gargano, and S. Perennes, Optimal sequential gossiping by short messages, Discrete Applied Mathematics, vol.86, issue.2-3, pp.145-155, 1998.
DOI : 10.1016/S0166-218X(98)00022-5

J. Bermond, L. Gargano, A. A. Rescigno, and U. Vaccaro, Fast Gossiping by Short Messages, SIAM Journal on Computing, vol.27, issue.4, pp.917-941, 1998.
DOI : 10.1137/S0097539795283619

J. Bermond, T. Kodate, and S. Perennes, Gossiping in cayley graphs by packets, Proceedings of 8-th Franco-Japanese, 4-th Franco-Chinese Conference on Combinatorics and Computer Science, pp.301-315, 1995.
DOI : 10.1007/3-540-61576-8_91

J. Bermond and J. Peters, Efficient gathering in radio grids with interference, Sep-tì emes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'05) Presqu'? ?le de Giens, pp.103-106, 2005.

P. Bertin, J. Bresse, and B. L. Sage, Accès haut débit en zone rurale: une solution " ad hoc, France Telecom R&D, vol.22, pp.16-18, 2005.

G. Bianchi, Performance analysis of the IEEE 802.11 distributed coordination function, IEEE Journal on Selected Areas in Communications, vol.18, issue.3, pp.535-547, 2000.
DOI : 10.1109/49.840210

V. Bonifaci, P. Korteweg, A. Marchetti-spaccamela, and L. Stougie, An approximation algorithm for the wireless gathering problem, 10th Scandinavian Workshop on Algorithm Theory (SWAT), 2006.

I. Chlamtac and O. Weinstein, The wave expansion approach to broadcasting in multihop radio networks, IEEE Transactions on Communications, vol.39, issue.3, pp.426-433, 1991.
DOI : 10.1109/26.79285

M. Christersson, L. Gasieniec, and A. Lingas, Gossiping with Bounded Size Messages in ad hoc Radio Networks, Proceedings of 29th International Colloquium on Automata, Languages and Programming, pp.377-389, 2002.
DOI : 10.1007/3-540-45465-9_33

M. Chrobak, L. Gasieniec, and W. Rytter, Fast broadcasting and gossiping in radio networks, Journal of Algorithms, vol.43, issue.2, pp.177-189, 2002.
DOI : 10.1016/S0196-6774(02)00004-4

S. A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing , STOC '71, pp.151-158, 1971.
DOI : 10.1145/800157.805047

M. L. Elkin and G. Kortsarz, Logarithmic inapproximability of the radio broadcast problem, Journal of Algorithms, vol.52, issue.1, pp.8-25, 2004.
DOI : 10.1016/j.jalgor.2003.11.004

I. Gaber and Y. Mansour, Centralized broadcast in multihop radio networks, Journal of Algorithms, vol.46, issue.1, pp.1-20, 2003.
DOI : 10.1016/S0196-6774(02)00292-4

J. Galtier, Optimizing the IEEE 802.11b performance using slow congestion window decrease, Proc. 16th ITC Specialist Seminar on Performance Evaluation of Wireless and Mobile Systems, pp.165-176, 2004.

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, pp.193-205, 2002.
DOI : 10.1007/978-0-387-35608-2_17

J. Hastad, Clique is hard to approximate within n/sup 1-??/, Proceedings of 37th Conference on Foundations of Computer Science, pp.105-142, 1999.
DOI : 10.1109/SFCS.1996.548522

J. Hromkovic, R. Klasing, A. Pelc, P. Ruzicka, and W. Unger, Dissemination of Information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00307029

R. Klasing, N. Morales, and S. Perennes, On the complexity of bandwidth allocation in radio networks with steady traffic demands, 2004.
URL : https://hal.archives-ouvertes.fr/inria-00070575

P. Mühlethaler, 11 et les réseaux sans fil, Eyrolles, vol.802, 2002.

. 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

I. Unité-de-recherche and . 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