@. Otherwise, > ?(s 2 ), the traffic is routed via the tunnel (?(s 1 ), ? 2 (s 1 )), and we have two subproblems with two sources: OP T ? (?(s 1 ), ?(s 2 ); [?(s 2 ), ? 2 (s 1 )? 1]) and ) See Figure 8 for an illus- tration

. Lemma-3, Suppose we have two nodes i and j, with i < j, i carrying the traffic of one source and j the traffic of the other source Suppose also that the traffic is destined to nodes in [j, u]. Let (i, ?(i)) denotes the longest tunnel from i (with ?(i) ? u) If ?(i) > j, then there exists an optimal solution where the traffic of i destined for the nodes in [?(i), u] uses as first tunnel (i, ?(i))

]. S. Arora, Nearly linear time approximation schemes for Euclidean TSP and other geometric problems, Proceedings 38th Annual Symposium on Foundations of Computer Science, pp.554-563, 1997.
DOI : 10.1109/SFCS.1997.646145

J. Bermond, D. Coudert, J. Moulierac, S. Pérennes, I. Sau et al., Designing Hypergraph Layouts to GMPLS Routing Strategies, Proc. of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp.57-71, 2009.
DOI : 10.1109/TCOMM.2008.050601
URL : https://hal.archives-ouvertes.fr/inria-00428685

J. Bermond, D. Coudert, J. Moulierac, S. Pérennes, I. Sau et al., GMPLS label space minimization through hypergraph layouts, Theoretical Computer Science, vol.444, 2009.
DOI : 10.1016/j.tcs.2012.01.033
URL : https://hal.archives-ouvertes.fr/inria-00426681

J. Bermond, N. Marlin, D. Peleg, and S. Pérennes, Directed virtual path layouts in ATM networks, Theoretical Computer Science, vol.291, issue.1, pp.3-28, 2003.
DOI : 10.1016/S0304-3975(01)00394-2
URL : https://hal.archives-ouvertes.fr/inria-00073007

M. Bern and P. Plassmann, The Steiner problem with edge lengths 1 and 2, Information Processing Letters, vol.32, issue.4, pp.171-176, 1989.
DOI : 10.1016/0020-0190(89)90039-2

S. Bhatnagar, S. Ganguly, and B. Nath, Creating multipoint-to-point LSPs for traffic engineering, IEEE Communications Magazine, vol.43, issue.1, pp.95-100, 2005.
DOI : 10.1109/MCOM.2005.1381881

M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel et al., Approximation Algorithms for Directed Steiner Problems, Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.192-200, 1998.
DOI : 10.1006/jagm.1999.1042

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

O. Gerstel, A. Wool, and S. Zaks, Optimal layouts on a chain ATM network, Discrete Applied Mathematics, vol.83, issue.1-3, pp.157-178, 1998.
DOI : 10.1016/S0166-218X(98)80002-4

M. X. Goemans, A. V. Goldberg, S. Plotkin, D. B. Shmoys, E. Tardos et al., Improved approximation algorithms for network design problems, Proc. of the 5th annual ACM- SIAM symposium on Discrete algorithms (SODA), pp.223-232, 1994.

A. Gupta, A. Kumar, and R. Rastogi, Exploring the trade-off between label size and stack depth in MPLS routing, Proc. of IEEE INFOCOM, pp.544-554, 2003.

A. Gupta, A. Kumar, and R. Rastogi, Traveling with a Pez Dispenser (or, Routing Issues in MPLS), SIAM Journal on Computing, vol.34, issue.2, pp.453-474, 2005.
DOI : 10.1137/S0097539702409927

A. Gupta, A. Kumar, and M. Thorup, Tree based MPLS routing, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures , SPAA '03, pp.193-199, 2003.
DOI : 10.1145/777412.777443

S. Khuller and U. Vishkin, Biconnectivity approximations and graph carvings, Journal of the ACM, vol.41, issue.2, pp.214-235, 1994.
DOI : 10.1145/174652.174654

F. Ramos, IST-LASAGNE: towards all-optical label swapping employing optical logic gates and optical flip-flops, Journal of Lightwave Technology, vol.23, issue.10, pp.2993-3011, 2005.
DOI : 10.1109/JLT.2005.855714

R. Raz and S. Safra, A sub-constant error-probability low-degree test, and a sub-constant errorprobability PCP characterization of NP, Proc. of the 29th annual ACM Symposium on Theory of Computing (STOC), pp.475-484, 1997.

H. Saito, Y. Miyao, and M. Yoshida, Traffic engineering using multiple multipoint-to-point LSPs, Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064), pp.894-901, 2000.
DOI : 10.1109/INFCOM.2000.832264

F. Solano-donado, R. V. Caenegem, D. Colle, J. L. Marzo, M. Pickavet et al., All-Optical Label Stacking: Easing the Trade-offs Between Routing and Architecture Cost in All-Optical Packet Switching, IEEE INFOCOM 2008, The 27th Conference on Computer Communications, pp.655-663, 2008.
DOI : 10.1109/INFOCOM.2008.115

F. Solano-donado, R. Fabregat, and J. Marzo, On optimal computation of MPLS label binding for multipoint-to-point connections, IEEE Transactions on Communications, vol.56, issue.7, pp.1056-1059, 2007.
DOI : 10.1109/TCOMM.2008.050601

F. Solano-donado and J. Moulierac, Routing in all-optical label switched-based networks with small label spaces, 13th Conference on Optical Network Design and Modeling (ONDM), p.6, 2009.
URL : https://hal.archives-ouvertes.fr/inria-00425298

F. Solano-donado, T. Stidsen, R. Fabregat, and J. Marzo, Label Space Reduction in MPLS Networks: How Much Can A Single Stacked Label Do?, IEEE/ACM Transactions on Networking, vol.16, issue.6, pp.1308-1320, 2008.
DOI : 10.1109/TNET.2007.912382

R. E. Tarjan, Depth-First Search and Linear Graph Algorithms, SIAM Journal on Computing, vol.1, issue.2, pp.146-160, 1972.
DOI : 10.1137/0201010

V. Vazirani, Approximation Algorithms, 2003.
DOI : 10.1007/978-3-662-04565-7