N. Alon, D. Moshkovitz, and S. Safra, -restrictions, ACM Transactions on Algorithms, vol.2, issue.2, pp.153-177, 2006.
DOI : 10.1145/1150334.1150336
URL : https://hal.archives-ouvertes.fr/halshs-00480214

L. D. Andersen, The strong chromatic index of a cubic graph is at most 10, Discrete Mathematics, vol.108, issue.1-3, pp.231-252, 1992.
DOI : 10.1016/0012-365X(92)90678-9

S. Athanassopoulos, I. Caragiannis, C. Kaklamanis, and E. Papaioannou, Energy-Efficient Communication in Multi-interface Wireless Networks, Proc. of the 34th Int. Symp. on Mathematical Foundations of Computer Science (MFCS), pp.102-111, 2009.
DOI : 10.1006/jagm.2000.1086

P. Bahl, A. Adya, J. Padhye, and A. Walman, Reconsidering wireless systems with multiple radios, ACM SIGCOMM Computer Communication Review, vol.34, issue.5, pp.39-46, 2004.
DOI : 10.1145/1039111.1039122

F. Barsi, A. Navarra, and M. C. Pinotti, Cheapest Paths in Multi-interface Networks, Proc. of the 10th Int. Conf. on Distributed Computing and Networking (ICDCN), pp.37-42, 2009.
DOI : 10.1007/978-3-540-68111-3_110

S. Basagni, F. Nidito, and A. Farago, The multi-radio advantage, 2009 IEEE Radio and Wireless Symposium, pp.478-481, 2009.
DOI : 10.1109/RWS.2009.4957392

H. L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, vol.25, issue.6, pp.1305-1317, 1996.
DOI : 10.1137/S0097539793251219

F. Bruera, S. Cicerone, G. D. Angelo, G. D. Stefano, and D. Frigioni, Dynamic Multi-level Overlay Graphs for Shortest Paths, Mathematics in Computer Science, vol.1, issue.4, pp.709-736, 2008.
DOI : 10.1007/s11786-007-0023-5

M. Caporuscio, D. Charlet, V. Issarny, and A. Navarra, Energetic performance of service-oriented multi-radio networks, Proceedings of the 6th international workshop on Software and performance , WOSP '07, pp.42-45, 2007.
DOI : 10.1145/1216993.1217002
URL : https://hal.archives-ouvertes.fr/inria-00110341

D. Cavalcanti, H. Gossain, and D. Agrawal, Connectivity in Multi-Radio, Multi-Channel Heterogeneous AD HOC Networks, 2005 IEEE 16th International Symposium on Personal, Indoor and Mobile Radio Communications, pp.1322-1326, 2005.
DOI : 10.1109/PIMRC.2005.1651655

M. Chrobak and D. Eppstein, Planar orientations with low out-degree and compaction of adjacency matrices, Theoretical Computer Science, vol.86, issue.2, pp.243-266, 1991.
DOI : 10.1016/0304-3975(91)90020-3

G. D. Angelo, G. D. Stefano, and A. Navarra, Minimizing the Maximum Duty for Connectivity in Multi-Interface Networks, Proc. of the 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA), pp.254-267, 2010.

G. D. Angelo, G. D. Stefano, and A. Navarra, Bandwidth Constrained Multi-Interface Networks, Proc. of the 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOF- SEM), pp.202-213, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00644104

G. D. Angelo, G. D. Stefano, and A. Navarra, Min-Max Coverage in Multi- Interface Networks, Proc. of the 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), pp.190-201, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00644084

R. Draves, J. Padhye, and B. Zill, Routing in multi-radio, multi-hop wireless mesh networks, Proceedings of the 10th annual international conference on Mobile computing and networking , MobiCom '04, pp.114-128, 2004.
DOI : 10.1145/1023720.1023732

A. Faragó and S. Basagni, The effect of multi-radio nodes on network connectivity -- a graph theoretic analysis, 2008 IEEE 19th International Symposium on Personal, Indoor and Mobile Radio Communications, 2008.
DOI : 10.1109/PIMRC.2008.5173153

D. Frigioni, A. Marchetti-spaccamela, and U. Nanni, Semidynamic Algorithms for Maintaining Single-Source Shortest Path Trees, Algorithmica, vol.22, issue.3, pp.250-274, 1998.
DOI : 10.1007/PL00009224
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.9698

H. Gabow and H. Westermann, Forests, frames, and games: algorithms for matroid sums and applications, Proceedings of the twentieth annual ACM symposium on Theory of computing , STOC '88, pp.465-497, 1992.
DOI : 10.1145/62212.62252

M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, 1979.

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

R. Klasing, A. Kosowski, and A. Navarra, Cost minimization in wireless networks with a bounded and unbounded number of interfaces, Networks, vol.43, issue.3, pp.266-275, 2009.
DOI : 10.1002/net.20266

A. Kosowski, A. Navarra, and M. C. Pinotti, Exploiting multi-interface networks: Connectivity and Cheapest Paths, Wireless Networks, vol.53, issue.3, pp.1063-1073, 2010.
DOI : 10.1007/s11276-009-0188-8
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.417.8214

S. M. Malitz, Genus g Graphs Have Pagenumber O(???g), Journal of Algorithms, vol.17, issue.1, pp.85-109, 1994.
DOI : 10.1006/jagm.1994.1028