K. Alzoubi, P. Wan, and O. Frieder, MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS, International Journal of Foundations of Computer Science, vol.14, issue.02, pp.287-303, 2003.
DOI : 10.1142/S012905410300173X

D. M. Blough, M. Leoncini, G. Resta, and P. Santi, The K-neigh protocol for symmetric topology control in ad hoc networks, in proc, of the 4th ACM Int. Symp. on Mobile Ad Hoc Networking and Computing, 2003.

M. C?galj, J. Hubaux, and C. Enz, Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues, in proc, of the Eighth ACM International Conference on Mobile Networking and Computing, 2002.

M. C?galj, J. Hubaux, and C. Enz, Energy-efficient broadcasting in all-wireless networks

B. Chen, K. Jamieson, H. Balakrishnan, and R. , Morris Span: an energy efficient coordination algorithm for topology maintenance in ad hoc wireless networks, ACM MobiCom, pp.85-96, 2001.

Y. P. Chen and A. L. Liestman, Approximating Minimum Size Weakly-Connected Dominating Sets for Clustering Mobile Ad Hoc Networks, in proc, of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp.165-172, 2002.

A. Clementi, P. Crescenzi, P. Penna, G. Rossi, and P. Vocca, On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs, 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS'01), pp.121-131, 2001.
DOI : 10.1007/3-540-44693-1_11

T. Clausen and P. Jacquet, Optimized Link State Routing Protocol, IETF-RFC-3626

U. Feige, A threshold of ln n for approximating set cover, Journal of the ACM, vol.45, issue.4, pp.634-652, 1998.
DOI : 10.1145/285055.285059

L. Feeney and M. Nilsson, Investigating the energy consumption of a wireless network interface in an ad hoc networking environment, Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.01CH37213), 2001.
DOI : 10.1109/INFCOM.2001.916651

M. Garey and D. S. Johnson, Computers and Intractability: a guide to the Theory of NP- Completeness, 1979.

P. Gupta and P. R. Kumar, The capacity of wireless networks, IEEE Transactions on Information Theory, vol.46, issue.2, pp.46-388, 2000.
DOI : 10.1109/18.825799

V. Kann, Polynomially bounded minimization problems which are hard to approximate, Nordic Journal of Computing, vol.1, issue.3, pp.317-331, 1994.
DOI : 10.1007/3-540-56939-1_61

P. Jacquet, P. Minet, P. Mühlethaler, and N. Rivierre, Increasing Reliability in cable-free radio lans: low level forwarding in HiperLan, Wireless Personal Communications, vol.4, issue.1, pp.65-80, 1997.
DOI : 10.1023/A:1008867232482

D. S. Johnson, Approximation algorithms for combinatorial problems, Proceedings of the fifth annual ACM symposium on Theory of computing , STOC '73, pp.256-278, 1974.
DOI : 10.1145/800125.804034

A. Laouiti, A. Qayyum, and L. Viennot, Multipoint Relaying: An Efficient Technique for Flooding in, Mobile Wireless Networks, 35th Annual Hawaii International Conference on System Sciences, 2001.
URL : https://hal.archives-ouvertes.fr/inria-00072756

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

S. Narayanaswamy, V. Kawadia, R. S. Sreenivas, and P. R. Kumar, Power Control in Ad Hoc Networks: Theory, Architecture, Algorithm and Implementation of the COMPOW Protocol, in proc, of the European Wireless Conference ? Next Generation Wireless Networks: Technologies, Protocols, Services and Applications, pp.156-162, 2002.

M. R. Pearlman, J. Deng, B. Liang, and Z. J. Haas, Elective participation in ad hoc networks based on energy consumption, Global Telecommunications Conference, 2002. GLOBECOM '02. IEEE, 2002.
DOI : 10.1109/GLOCOM.2002.1188035

R. Ramanathan and R. Rosales-hain, Topology control of multihop wireless networks using transmit power adjustment, Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064), pp.404-413, 2000.
DOI : 10.1109/INFCOM.2000.832213

R. Wattenhofer, L. Li, P. Bahl, and Y. Wang, Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks, in proc, of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, 2001.

Y. Xu, J. Heidemann, and D. Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking , MobiCom '01, 2001.
DOI : 10.1145/381677.381685

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, 2004.

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