D. Cavin, Y. Sassib, and A. Schiper, Probabilistic broadcast for flooding in a wireless mobile ad hoc networks, Proceedings of IEEE Wireless Communications and Networking Conference, 2003.

J. Y. Halpern, Z. J. Hass, and L. Li, Gossip-based ad hoc routing, Proceedings of IEEE Computer and Communications Societies (INFOCOM), 2002.

S. Guha and S. Khuller, Approximation algorithm for connected dominating sets, Proceedings of European Symposium on Algorithms, pp.179-193, 1996.

P. Jacquet, C. Adjih, and L. Viennot, Computing connected dominated sets with multipoint relays Ad Hoc & Sensor Wireless Networks, pp.782-795, 2005.

C. E. Shannon, A Mathematical Theory of Communication, Bell System Technical Journal, vol.27, issue.3, pp.379-423, 1948.
DOI : 10.1002/j.1538-7305.1948.tb01338.x

S. R. Li, R. Ahlswede, N. Cai, and R. W. Yeung, Network information flow, IEEE Transactions on Information Theory, vol.46, issue.4, pp.1204-1216, 2000.

T. Ho, M. Medard, R. Kotter, J. Shi, M. Effros et al., A Random Linear Network Coding Approach to Multicast, IEEE Transactions on Information Theory, vol.52, issue.10, pp.4413-4430, 2006.
DOI : 10.1109/TIT.2006.881746

S. Egner, P. Sanders, and L. Tolhuizen, Polynomial time algorithm for network information flow, Proceedings of IEEE International Symposium on Information Theory (ISIT), 2003.

T. Ho, D. Karger, R. Koetter, M. Medard, and M. Effros, The benefits of coding over routing in a randomized setting, IEEE International Symposium on Information Theory, 2003. Proceedings., p.442, 2003.
DOI : 10.1109/ISIT.2003.1228459

P. A. Chou, Y. Wu, and S. Kung, Minimum-energy multicast in mobile ad hoc networks using network coding, IEEE Transactions on Communications, vol.53, issue.11, pp.1906-1918, 2005.

D. S. Lun, M. Medard, R. Rantnakar, D. R. Karger, R. Koetter et al., Minimum-cost multicast over coded packet networks, IEEE Transactions on Information Theory, vol.52, issue.6, pp.2608-2623, 2006.
DOI : 10.1109/TIT.2006.874523
URL : http://arxiv.org/abs/cs/0503064

C. Adjih, S. Y. Cho, and P. Jacquet, An association discovery protocol for hybrid wireless mesh networks, the 6th IFIP Annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net), 2007.

J. S. Park, D. S. Lun, M. Gerla, M. Medard, and Y. Yi, Codecast:a network-coding-based ad hoc multicast protocol, Wireless Communication, pp.76-81, 2006.

U. Lee, J. Yeh, J. S. Park, M. Gerla, and G. Pau, Codetorrent: Content distribution using network coding in vanets, international Workshop on Decentralized Resource Sharing in Mobile Computing and Networking (MobiShare'06), 2006.

S. , K. S. Chachuiski, M. Jennings, and D. Katabi, Trading structure for randomness in wireless opporunistic routing, Proceedings of annual meeting of the Special Interest Group on Data Communication (SIGCOMM), pp.105-113, 2006.

C. Barakat, A. A. Hamra, and T. Turletti, Network coding for wireless mesn networks: a case study, International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM '06), 2006.

R. Koetter, D. S. Lun, M. Medard, and M. Effros, On coding for reliable communication over packet networks, 2007.

B. Wiliams and T. Camp, Comparison of broadcasting techniques for mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing , MobiHoc '02, 2002.
DOI : 10.1145/513800.513825

G. Tsudik, C. Ho, K. Obraczka, and K. Viswanath, Flooding for reliable mujlticast in multi-hop ad hoc networks, proceedings of the international workshop on discrete algorithms and methods for mobile computing and communication (DIALM), pp.64-71, 1999.

D. Maltz, J. Jetcheva, Y. Hu, and D. Johnson, A simple protocol for multicast and broadcast in mobile ad hoc networks, 2001.

H. Lim and C. Kim, Multicast tree contrusction and flooding in wireless ad hoc networks, proceedings of the ACM international workshop on modeling, analysis and simultation of wireless and mobile systems (MSWIM), 2000.

W. Peng and X. Lu, Efficient broadcast in mobile ad hoc networks using connected dominating sets, Journal of software, 1999.

L. Lovasz, On the ratio of optimal integral and fractional covers, Discrete Mathematics, vol.13, issue.4, 1975.
DOI : 10.1016/0012-365X(75)90058-8

F. Dai and J. Wu, An extended localized alogirhtm for connected dominating set formation in ad hoc wireless networks, IEEE Transaction Parallel and Distributed Systems, pp.908-920, 2004.

J. Wu and F. Dai, Broadcasting in ad hoc networks based on self-prunning, Proceedings of IEEE Computer and Communications Societies (INFOCOM), 2003.

I. F. Akyildiz and X. W. Kiyon, Wireless mesh networks: A survey, Computer Network Journal, pp.65-80, 2005.

P. Kinney, Ieee 802.15 general interest in mesh networking, 2003.

B. Lewis, P. Piggin, and P. Whitehead, Mesh networks in fixed broadband wireless access: multipoint enhancements for the 802, 2003.

E. Royer, C. Perkins, and S. Das, Ad hoc on-demand distance vector routing (aodv), 2003.

F. Templin, R. Ogier, and M. Lewis, Topology dissemination based on reverse-path forwarding (tbrpf), 2004.

D. Maltz, D. Johnson, and Y. Hu, The dynamic source routing protocol for mobile ad hoc networks (dsr), 2004.

X. Hong, M. Gerla, G. Pei, and T. Chen, Fisheye state routing protocol (fsr) for ad hoc networks, 2001.

M. Perman, Z. J. Haas, and P. Samar, The zone routing protocol (zrp) for ad hoc networks, 2002.

J. , L. M. Jiang, and Y. C. Tay, Cluster based routing protocol (cbrp), 1999.

M. Gerla, Z. Lu-xiaoyan, K. Hong, C. Xu, and . Flores, Lanmar + olsr: A scalable, group oriented extension of olsr, OLSR Interop and Workshop, 2004.

J. Moy, Ospf anatomy of an internet routing protocol, 1998.

M. Nozaki, H. Okada, K. Mase, and B. Zhang, Low-overhead and low-processing strategy of sta association information for ra-olsr in ieee802.11s, 2007.

P. Jacquet, T. Clausen, and E. Baccelli, Ospf-style database exchange and reliable synchronization in the olsr, 2004.
URL : https://hal.archives-ouvertes.fr/inria-00070717

Y. Joseph, J. Halpern-zygmunt, L. Haas, and . Li, Gossip-based ad hoc routing, Proceedings of IEEE Computer and Communications Societies (INFOCOM), 2002.

P. Muhlethaler, P. Jacquet, P. Minet, 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.

J. L. Boudec, C. Fragouli, and J. Widmer, Network coding : an instanace primer, pp.63-68, 2006.

R. Yeung, S. R. Li, and N. Cai, Linear network coding, IEEE Transactions on Information Theory, vol.49, issue.2, pp.371-381, 2003.

R. Koetter and M. Medard, Beyond routing:an algebraic approach to network coding

S. Jaggi, P. Chou, P. Sanders, K. Jain, M. Effros et al., Polynomial Time Algorithms for Multicast Network Code Construction, IEEE Transactions on Information Theory, vol.51, issue.6, pp.1972-1982, 2005.
DOI : 10.1109/TIT.2005.847712

P. A. Chou, P. Sanders, and K. Jain, Low complexity algebraic network multicast codes, Proceedings of 15st ACM Symposium on Parallel Algorithms and Architecture, 2003.

Y. Wu, P. A. Chou, and K. Jain, Practical network coding, Proceedings of 51st Allerton Conference on Communication, Control and Computing, 2003.

A. Feinstein, P. Elias, and C. E. Shannon, Note on maximum flow through a network, IRE transaction on Information Theory, vol.2, pp.117-119, 1956.

L. R. Ford-jr and D. R. Fulkerson, Maximal flow through a network, Journal canadien de math??matiques, vol.8, issue.0, pp.399-404, 1956.
DOI : 10.4153/CJM-1956-045-5

K. Menger, Zur allgemeinen kurventheorie, Fundamenta Mathematicae, vol.10, pp.95-115, 1927.

E. A. Dinic, Algorithm for solution of a problem of maximum flow in network with power estimation, Soviet Math. Doklady, vol.11, pp.1277-1280, 1970.

J. Edmond and R. M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM, vol.19, issue.2, pp.248-264, 1972.
DOI : 10.1145/321694.321699

V. Andrew, R. E. Goldberg, and . Tarjan, A new approach to the maximum flow problem, Proceedings of ACM Symposium on Theory of Computing, pp.136-146, 1986.

R. Koetter, D. S. Lun, M. Medard, and M. Effros, Further results on coding for reliable communication over packet networks, Internatoinal Symposium on Information THeory (ISIT), 2005.

C. Fragouli, M. Jafarisiavoshani, and S. Diggavi, On subspace properties for randomized network coding, Information Theory Workshop (ITW), 2007.

J. Hubaux, M. Canalij, and C. Enz, The minimum-energy broadcast in all wireless networks: Np-completeness, Proceedings of IEEE/ACM International Conference on Mobile Computing and Networking (MobiCom), pp.172-182, 2002.

J. S. Park, F. Soldo, D. S. Lun, M. Medard, and M. Gerla, Performance of Network Coding in Ad Hoc Networks, MILCOM 2006, pp.1-6, 2006.
DOI : 10.1109/MILCOM.2006.302320

N. Karmarkar, A new polynomial time algorithm for linear programming, Combinatorica, pp.373-395, 1984.

D. Jiang, Z. Li, B. Li, and L. C. Lau, On achieving optimal throughput with network coding, Proceedings of IEEE Computer and Communications Societies, pp.2184-2194, 2005.

S. Katti, H. Rahul, D. Katabi, W. Hu, and M. Medard, The importance of being opportunistic: Practical network coding for wireless environments, Proceedings of 43rd International Conference on Communication, Control and Computing, 2005.

S. Katti, W. Hu, H. Rahul, M. Medard, D. Katabi et al., Xors in the air: Practical wireless network coding [70] S. Biswas and R. Morris. Exor:opportunistic multi-hop routing for wireless networks, Proceedings of annual meeting of the Special Interest Group on Data Communication (SIGCOMM) Proceedings of annual meeting of the Special Interest Group on Data Communication (SIGCOMM), 2005.

J. Bicker, D. S. De-couto, D. Aguayo, and R. Morris, A high-throughput path metric for multi-hop routing, Proceedings of IEEE/ACM International Conference on Mobile Computing and Networking (MobiCom), 2003.

C. Fragouli, J. Widmer, and J. L. Boudec, Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding, Proceedings of IEEE Computer and Communications Societies (INFOCOM), 2005.

J. Widmer, C. Fragouli, and J. L. Boudec, A network coding approach to energy efficient broadcasting: from theory to practice, Proceedings of 1st intenational Workshop on Network Coding, Theory, and Applications (NetCod), 2006.

Y. Li, J. Wang, and X. Wang, Network coding based multicast in internet, Proceedings of IEEE/ACM International Conference on Parallel Processing Workshops, p.44, 2007.

C. Colbourn, B. Clark, and D. Johnson, Unit disk graphs, Discrete Mathematics, vol.86, 1990.

R. Gowaikar, B. Hassibi, A. F. Dana, R. Palanki, and M. Effros, On the capacity of wireless erasure relay networks, International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings., p.401, 2004.
DOI : 10.1109/ISIT.2004.1365437

A. F. Dana, B. Hassibi, R. Gowaikar, R. Palanki, and M. Effros, Capacity of wireless erasure networks, IEEE Transactions on Information Theory, vol.52, issue.3, pp.789-804, 2006.
DOI : 10.1109/TIT.2005.864424

S. Deb, T. Ho, M. Effros, R. Koetter, D. R. Karger et al., Network coding for wireless applications: A brief tutorial, Proceedings of International Workshop on Wireless Ad-hoc Networks, 2005.

Y. Boykov and V. Kolmogorov, A experimental comparision of min-cut/max-flow algorithms for energy minimization in vision, IEEE transactions on pattern analysis and machine intelligence (PAMI), 2004.

P. Kohi and P. H. Torr, Efficiently solving dynamic markov random fields using graph cuts, Proceedings of International Conference on Computer Vision, 2005.

J. Shi, A. Ramamoorthy, and R. D. , On the capacity of network coding for random networks, IEEE transactions on information theory, vol.51, pp.2878-2885, 2005.

J. Meng, S. Aly, V. Kapoor, and A. Klappenecker, Bounds on the network coding capacity for wireless random networks, Third Workshop on Network Coding, 2007.

R. A. Costa and J. Barros, Dual Radio Networks: Capacity and Connectivity, 2007 5th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks and Workshops, 2007.
DOI : 10.1109/WIOPT.2007.4480075

S. Y. Cho, C. Adjih, and P. Jacquet, Near optimal broadcast with network coding in large sensor networks, Proceedings of the first workshop on Information Theory for Sensor Networks, 2007.
URL : https://hal.archives-ouvertes.fr/inria-00166617

M. Penrose, Random Geometric Graphs, Oxford Studies in Probability, 2003.
DOI : 10.1093/acprof:oso/9780198506263.001.0001

M. Kim, I. Lee, and G. Elber, Polynomial/rational approximation of minkowski sum boundary curves, Graphical Models and Image Processing, vol.69, pp.136-165, 1998.

R. J. Gardner and P. Gornchi, A brunn-minkowski inequality for the integer lattice. Transcations of the, pp.3995-4042, 2001.

J. Serra, Image Analysis and Mathematical Morphology, 1983.

K. Voss, Discrete Images, Objects and Functions in Z n, 1993.
DOI : 10.1007/978-3-642-46779-0

C. Adjih, S. Y. Cho, and P. Jacquet, Heuristics for network coding in wireless networks, Proceedings of International Wireless Networks (WICON), 2007.
URL : https://hal.archives-ouvertes.fr/inria-00158082

S. Y. Cho, C. Adjih, and P. Jacquet, Near optimal broadcast with network coding in large homogeneous networks, INRIA Research Report RR-6188, 2007.
URL : https://hal.archives-ouvertes.fr/inria-00145231

S. Y. Cho and C. Adjih, Wireless Broadcast with Network Coding: Dynamic Rate Selection, INRIA Research Report RR-6349, 2007.
DOI : 10.1007/978-0-387-09490-8_17
URL : https://hal.archives-ouvertes.fr/inria-00186577

C. Fragouli and E. Soljanin, A connection between network coding and convolutional codes, 2004 IEEE International Conference on Communications (IEEE Cat. No.04CH37577), 2004.
DOI : 10.1109/ICC.2004.1312584

E. F. Alaeddine, C. David, S. Kave, J. L. Boudec, and S. Yoav, A framework for network coding in challenged wireless network, Demonstrations of International Conference on a Mobile Systems, Applications and Services (MobiSys '06), 2006.