G. Ausiello, A. D. Atri, and M. Protasi, Structure preserving reductions among convex optimization problems, Journal of Computer and System Sciences, vol.21, issue.1, pp.136-153, 1980.
DOI : 10.1016/0022-0000(80)90046-X

P. Berman and T. Fujito, On approximation properties of the Independent set problem for degree 3 graphs, 4th International Workshop on Algorithms and Data Structures (WADS95), pp.449-460, 1995.
DOI : 10.1007/3-540-60220-8_84

R. Bhandari, Survivable Networks: Algorithms for Diverse Routing, 1998.

A. Björklund, T. Husfeldt, and M. Koivisto, Set Partitioning via Inclusion-Exclusion, SIAM Journal on Computing, vol.39, issue.2, pp.546-563, 2009.
DOI : 10.1137/070683933

H. Broersma, X. Li, G. Woeginger, and S. Zhang, Paths and cycles in colored graphs, Australas. J. Combin, vol.31, pp.299-311, 2005.

F. Carrabs, R. Cerulli, and M. Gentili, The labeled maximum matching problem, Computers & Operations Research, vol.36, issue.6, pp.1859-1871, 2009.
DOI : 10.1016/j.cor.2008.05.012

R. Cerulli, P. Dell-'olmo, M. Gentili, and A. Raiconi, Heuristic approaches for the Minimum Labelling Hamiltonian Cycle Problem, Electronic Notes in Discrete Mathematics, vol.25, pp.131-138, 2006.
DOI : 10.1016/j.endm.2006.06.080

R. Cerulli, A. Fink, M. Gentili, and S. Voß, The Next Wave on Computing, Optimization, and Decision Technologies, chapter Metaheuristics comparison for the minimum labelling spanning tree problem, pp.93-106, 2005.

R. Cerulli, A. Fink, M. Gentili, and S. Voß, Extensions of the minimum labelling spanning tree problem, Journal of Telecommunications and Information Technology, vol.4, pp.39-45, 2006.

V. T. Chakaravarthy, New results on the computability and complexity of points?to analysis, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL '03, pp.115-125, 2003.

R. Chang and S. Leu, The minimum labeling spanning trees, Information Processing Letters, vol.63, issue.5, pp.277-282, 1997.
DOI : 10.1016/S0020-0190(97)00127-0

D. Coudert, P. Datta, S. Perennes, H. Rivano, and M. Voge, SHARED RISK RESOURCE GROUP COMPLEXITY AND APPROXIMABILITY ISSUES, Parallel Processing Letters, vol.17, issue.02, pp.169-184, 2007.
DOI : 10.1142/S0129626407002958

URL : https://hal.archives-ouvertes.fr/hal-00371100

D. Coudert, S. Perennes, H. Rivano, and M. Voge, Shared risk resource groups and colored graph: Polynomial and FPT optimisation problems

B. Couëtoux, L. Gourvès, J. Monnot, and O. A. Telelis, Labeled Traveling Salesman Problems: Complexity and approximation, Discrete Optimization, vol.7, issue.1-2, pp.74-85, 2010.
DOI : 10.1016/j.disopt.2010.02.003

P. Datta and A. K. Somani, Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures, Computer Networks, vol.52, issue.12, pp.2381-2394, 2008.
DOI : 10.1016/j.comnet.2008.04.017

J. Doucette and W. Grover, Shared-Risk Logical Span Groups in Span-Restorable Optical Networks: Analysis and Capacity Planning Model, Photonic Network Communications, vol.18, issue.10, pp.35-53, 2005.
DOI : 10.1007/s11107-005-4530-5

R. G. Downey and M. R. Fellows, Fixed-parameter tractability and completeness II: On completeness for W[1], Theoretical Computer Science, vol.141, issue.1-2, pp.109-131, 1995.
DOI : 10.1016/0304-3975(94)00097-3

A. Faragó, A graph theoretic model for complex network failure scenarios, 8th INFORMS Telecommunications Conference, 2006.

M. R. Fellows, J. Guob, and I. Kanj, The parameterized complexity of some minimum label problems, Journal of Computer and System Sciences, vol.76, issue.8, pp.727-740, 2010.
DOI : 10.1016/j.jcss.2010.02.012

M. Garey and D. Johnson, Computers and Intractability: A Guide to the theory of NPcompleteness, Freeman NY, 1979.

R. Hassin, J. Monnot, and D. Segev, Approximation algorithms and hardness results for??labeled connectivity problems, Journal of Combinatorial Optimization, vol.33, issue.1, pp.437-453, 2007.
DOI : 10.1007/s10878-007-9044-x

R. Hassin, J. Monnot, and D. Segev, The complexity of bottleneck labeled graph problems, 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp.328-340, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00917828

J. E. Hopcroft and R. E. Tarjan, Algorithm 447: efficient algorithms for graph manipulation, Communications of the ACM, vol.16, issue.6, pp.372-378, 1973.
DOI : 10.1145/362248.362272

J. E. Hopcroft and R. E. Tarjan, Dividing a Graph into Triconnected Components, SIAM Journal on Computing, vol.2, issue.3, pp.135-158, 1973.
DOI : 10.1137/0202012

J. Q. Hu, Diverse routing in mesh optical networks, IEEE Transactions on Communications, vol.51, pp.489-494, 2003.

Q. Jiang, D. S. Reeves, and P. Ning, Improving Robustness of PGP Keyrings by Conflict Detection, RSA Conference Cryptographers' Track (CT-RSA), pp.194-207, 2004.
DOI : 10.1007/978-3-540-24660-2_16

V. Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters, vol.37, issue.1, pp.27-35, 1991.
DOI : 10.1016/0020-0190(91)90246-E

S. O. Krumke and H. Wirth, On the minimum label spanning tree problem, Information Processing Letters, vol.66, issue.2, pp.81-85, 1998.
DOI : 10.1016/S0020-0190(98)00034-9

X. Luo and B. Wang, Diverse routing in WDM optical networks with shared risk link group (SRLG) failures, Proc. DRCN, pp.445-452, 2005.

R. Niedermeier, Invitation to fixed-parameter algorithms. Oxford lecture series in mathematics and its applications, 2006.

L. Shen, X. Yang, and B. Ramamurthy, Shared-risk link group (SRLG)-diverse path provisioning under hybrid service level agreements in wavelength-routed optical mesh networks: formulation and solution approaches, OptiComm 2003: Optical Networking and Communications, pp.918-931, 2005.
DOI : 10.1117/12.533306

S. Szeider, Finding paths in graphs avoiding forbidden transitions, Discrete Applied Mathematics, vol.126, issue.2-3, pp.261-273, 2003.
DOI : 10.1016/S0166-218X(02)00251-2

Y. Wan, G. Chen, and Y. Xu, A note on the minimum label spanning tree, Information Processing Letters, vol.84, issue.2, pp.99-101, 2002.
DOI : 10.1016/S0020-0190(02)00230-2

S. Yuan, S. Varma, and J. P. Jue, Minimum-color path problems for reliability in mesh networks, Proc. IEEE INFOCOM, pp.2658-2669, 2005.