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

R. Gowaikar, . Dana, F. Amir, R. Palanki, . Hassibi et al., On the capacity of wireless erasure relay networks, International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings., 2004.
DOI : 10.1109/ISIT.2004.1365437

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

Y. Wu, P. A. Chou, 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.
DOI : 10.1109/TCOMM.2005.857148

D. S. Lun, N. Ratnakar, M. Médard, R. Koetter, D. R. Karger 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

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

D. S. Lun, M. Médard, R. Koetter, and M. Effros, On coding for reliable communication over packet networks, Physical Communication, vol.1, issue.1, 2007.
DOI : 10.1016/j.phycom.2008.01.006

A. Ramamoorthy, R. D. Shi, and . Wesel, On the Capacity of Network Coding for Random Networks, IEEE Transactions on Information Theory, vol.51, issue.8, pp.2878-2885, 2005.
DOI : 10.1109/TIT.2005.851725

S. A. Aly, V. Kapoor, J. Meng, and A. Klappenecker, Bounds on the Network Coding Capacity for Wireless Random Networks, 2007 Information Theory and Applications Workshop, 2007.
DOI : 10.1109/ITA.2007.4357585

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

B. Clark, C. Colbourn, and D. Johnson, Unit disk graphs, Discrete Mathematics, vol.86, pp.1-3, 1990.
DOI : 10.1016/s0167-5060(08)71047-1

C. Fragouli, J. Widmer, and J. L. Boudec, A Network Coding Approach to Energy Efficient Broadcasting, Proceedings of INFOCOM 2006, 2006.

I. K. Lee, M. S. Kim, and G. Elber, Polynomial/Rational Approximation of Minkowski Sum Boundary Curves, Graphical Models and Image Processing, vol.60, issue.2, pp.136-165, 1998.
DOI : 10.1006/gmip.1998.0464

R. J. Gardner and P. Gronchi, A Brunn-Minkowski inequality for the integer lattice, Transactions of the American Mathematical Society, vol.353, issue.10, pp.3995-4042, 2001.
DOI : 10.1090/S0002-9947-01-02763-5

P. A. Chou, W. Yunnan, and K. Jain, Practical Network Coding, Forty-third Annual Allerton Conference on Communication, Control, and Computing, 2003.

S. R. Li, R. W. Yeung, and N. Cai, Linear network coding, IEEE Transactions on Information Theory, vol.49, issue.2, 2003.
DOI : 10.1109/TIT.2002.807285
URL : https://hal.archives-ouvertes.fr/hal-01327498

R. Koetter and M. Medard, An algebraic approach to network coding, IEEE/ACM Transactions on Networking, vol.11, issue.5, 2003.

E. Deb, . Ho, . Karger, . Koetter, . Lun et al., Network Coding for Wireless Application: A Brief Tutorial, Proc. International Workshop on Wireless Ad-Hoc Networks (IWWAN), 2005.

J. Widmer, C. Fragouli, and J. Boudec, Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding, 2005.

J. Wu and F. Dai, Efficient Broadcasting with Guaranteed Coverage in Mobile Ad Hoc Networks, IEEE Transactions on Mobile Computing, vol.4, issue.3, pp.1-12, 2005.

D. Katabi, S. Katti, W. Hu, H. Rahul, and M. Médard, On Practical Network Coding for Wireless Environments, 2006 International Zurich Seminar on Communications, 2006.
DOI : 10.1109/IZS.2006.1649085

D. S. Lun, M. Médard, and R. Koetter, Network Coding for Efficient Wireless Unicast, 2006 International Zurich Seminar on Communications, 2006.
DOI : 10.1109/IZS.2006.1649082

A. Hamra, C. Barakat, and T. Turletti, Network Coding for Wireless Mesh Networks: A Case Study, 2006 International Symposium on a World of Wireless, Mobile and Multimedia Networks(WoWMoM'06), 2006.
DOI : 10.1109/WOWMOM.2006.78

J. S. Park, D. S. Lun, F. Soldo, M. Gerla, and M. Médard, Performance of Network Coding in Ad Hoc Networks, MILCOM 2006, 2006.
DOI : 10.1109/MILCOM.2006.302320

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

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

R. Kimmel, Numerical Geometry of Images: theory, algorithms, and applications, 2004.
DOI : 10.1007/978-0-387-21637-9

Y. Boykov and V. Kolmogorov, An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004.

P. Kohli and P. H. Torr, Efficiently solving dynamic Markov random fields using graph cuts, Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, 2005.
DOI : 10.1109/ICCV.2005.81
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.399.3048

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.