C. C. Aggarwal and H. Wang, Graph data management and mining: A survey of algorithms and applications , Managing and Mining Graph Data Advances in Database Systems, pp.13-68, 2010.

P. Alimonti and V. Kann, Some APX-completeness results for cubic graphs, Theoretical Computer Science, vol.237, issue.1-2, pp.123-134, 2000.
DOI : 10.1016/S0304-3975(98)00158-3

H. K. Anheier, J. Gerhards, and F. P. Romo, Forms of Capital and Social Structure in Cultural Fields: Examining Bourdieu's Social Topography, American Journal of Sociology, vol.100, issue.4, pp.859-903, 1995.
DOI : 10.1086/230603

H. Broersma, X. Li, G. J. Woeginger, and S. Zhang, Paths and Cycles in Colored Graphs, Australasian Journal on Combinatorics, vol.31, pp.299-311, 2005.

M. R. Cerioli, L. Faria, T. O. Ferreira, C. A. Martinhon, F. Protti et al., Partition into cliques for cubic graphs: Planar case, complexity and approximation, Discrete Applied Mathematics, vol.156, issue.12, pp.2270-2278, 2008.
DOI : 10.1016/j.dam.2007.10.015

L. S. Chandran and L. S. Ram, On the relationship between ATSP and the cycle cover problem, Theoretical Computer Science, vol.370, issue.1-3, pp.218-228, 2007.
DOI : 10.1016/j.tcs.2006.10.026

Z. Chen, Y. Okamoto, and L. Wang, Improved deterministic approximation algorithms for Max TSP, Information Processing Letters, vol.95, issue.2, pp.333-342, 2005.
DOI : 10.1016/j.ipl.2005.03.011

Z. Chen and T. Nagoya, Improved approximation algorithms for metric MaxTSP, Journal of Combinatorial Optimization, vol.7, issue.4, pp.321-336, 2007.
DOI : 10.1007/s10878-006-9023-7

B. Couëtoux, L. Gourvès, J. Monnot, and O. A. , On Labeled Traveling Salesman Problems, Lecture Notes in Computer Science, vol.5369, pp.776-787, 2008.
DOI : 10.1007/978-3-540-92182-0_68

M. Deng, Q. Liu, J. Wang, and Y. Shi, A general method of spatio-temporal clustering analysis, Science China Information Sciences, vol.20, issue.10, pp.1-14, 2013.
DOI : 10.1007/s11432-011-4391-8

E. S. El-mallah and C. J. Colbourn, The complexity of some edge deletion problems, IEEE Transactions on Circuits and Systems, vol.35, issue.3, pp.354-362, 1988.
DOI : 10.1109/31.1748

L. Freeman, The Development of Social Network Analysis, 2006.

M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NPcompleteness, 1979.

A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, Parallel Symmetry-Breaking in Sparse Graphs, SIAM Journal on Discrete Mathematics, vol.1, issue.4, pp.434-446, 1988.
DOI : 10.1137/0401044

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, Proc. of WG'07, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00917828

Z. Jin, M. Kano, X. Li, and B. Wei, Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees, Journal of Combinatorial Optimization, vol.91, issue.2, pp.445-454, 2006.
DOI : 10.1007/s10878-006-8460-7

H. Kaplan, M. Lewenstein, N. Shafrir, and M. I. Sviridenko, Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs, Journal of the ACM, vol.52, issue.4, pp.602-626, 2005.
DOI : 10.1145/1082036.1082041

M. Kano and X. Li, Monochromatic and heterochromatic subgraphs in edge-colored graphs -a survey, Graphs Combin, pp.237-263, 2008.

S. O. Krumke and H. C. 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

C. P. Kruskal, L. Rudolph, and M. Snir, Efficient parallel algorithms for graph problems, Algorithmica, vol.34, issue.1-4, pp.43-64, 1990.
DOI : 10.1007/BF01840376

P. L. Lai and M. Y. Chiu, Uniform disjoint cycle covers on a hierarchical multicomputer system, Security-Enriched Urban Computing and Smart Grid, CCIS, vol.223, pp.141-148, 2011.

X. Li and X. Y. Zhang, On the minimum monochromatic or multicolored subgraph partition problems, Theoretical Computer Science, vol.385, issue.1-3, pp.1-10, 2007.
DOI : 10.1016/j.tcs.2007.04.033

B. Liu, Web data mining: exploring hyperlinks, Contents, and Usage Data, 2011.
DOI : 10.1007/978-3-642-19460-3

L. Lovász and M. D. Plummer, Matching theory, 1986.
DOI : 10.1090/chel/367

G. Macgillivray and M. Yu, Generalized partitions of graphs, Discrete Applied Mathematics, vol.91, issue.1-3, pp.143-153, 1999.
DOI : 10.1016/S0166-218X(98)00124-3

B. Manthey, On Approximating Restricted Cycle Covers, SIAM Journal on Computing, vol.38, issue.1, pp.181-206, 2008.
DOI : 10.1137/060676003

B. Manthey, Minimum-weight cycle covers and their approximability, Discrete Applied Mathematics, vol.157, issue.7, pp.1470-1480, 2009.
DOI : 10.1016/j.dam.2008.10.005

J. Monnot, The labeled perfect matching in bipartite graphs, Information Processing Letters, vol.96, issue.3, pp.81-88, 2005.
DOI : 10.1016/j.ipl.2005.06.009

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

T. Nishi and L. O. Chua, Topological proof of the Nielsen - Willson theorem, IEEE Transactions on Circuits and Systems, vol.33, issue.4, pp.398-405, 1986.
DOI : 10.1109/TCS.1986.1085935

C. H. Papadimitriou and M. , Optimization, approximation, and complexity classes, Journal of Computer and System Sciences, vol.43, issue.3, pp.425-440, 1991.
DOI : 10.1016/0022-0000(91)90023-X

B. Paten, M. Diekhans, D. Earl, J. St, J. John et al., Cactus graphs for genome comparisons, Lecture Notes in Bioinformatics, vol.6044, pp.410-425, 2010.

S. Wasserman and K. Faust, Social network analysis: Methods and applications (structural analysis in the social sciences), 1994.
DOI : 10.1017/CBO9780511815478

V. Yegnanarayanan, Graph colourings and partitions, Theoretical Computer Science, vol.263, issue.1-2, pp.59-74, 2001.
DOI : 10.1016/S0304-3975(00)00231-0