D. Ahr, J. Békési, G. Galambos, M. Oswald, and G. Reinelt, An exact algorithm for scheduling identical coupled tasks, Mathematical Methods of Operations Research (ZOR), vol.59, issue.2, pp.193-203, 2004.
DOI : 10.1007/s001860300328

S. , R. Arikati, and C. Pandu-rangan, Linear algorithm for optimal path cover problem on interval graphs, Information Processing Letters, vol.35, issue.3, pp.149-153, 1990.

P. Berman and M. Karpinski, 8/7-approximation algorithm for (1,2)-TSP, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm , SODA '06, pp.641-648, 2006.
DOI : 10.1145/1109557.1109627

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.70.8593

J. Bla?ewicz, K. Ecker, T. Kis, C. N. Potts, M. Tanas et al., Scheduling of coupled tasks with unit processing times, Journal of Scheduling, vol.27, issue.10, 2009.
DOI : 10.1007/s10951-010-0167-z

F. T. Boesch, S. Chen, and B. Mchugh, On covering the points of a graph with point disjoint paths, Graphs and Combinatorics, vol.406, pp.201-212, 1974.
DOI : 10.1007/BFb0066442

. Ph, C. Chrétienne, and . Picouleau, Scheduling with communication delays: a survey, Scheduling theory and its applications, pp.641-648, 1995.

P. Detti and C. Meloni, A linear algorithm for the Hamiltonian completion number of the line graph of a cactus, Discrete Applied Mathematics, vol.136, issue.2-3, pp.197-215, 2004.
DOI : 10.1016/S0166-218X(03)00441-4

M. R. Garey and D. S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness, 1979.

S. E. Goodman, S. T. Hedetniemi, and P. J. Slater, Advances on the Hamiltonian Completion Problem, Journal of the ACM, vol.22, issue.3, pp.352-360, 1975.
DOI : 10.1145/321892.321897

R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. Kan, Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey, Annals of Discrete Mathematics, vol.5, pp.287-326, 1979.
DOI : 10.1016/S0167-5060(08)70356-X

R. Hung and M. Chang, Solving the path cover problem on circular-arc graphs by using an approximation algorithm, Discrete Applied Mathematics, vol.154, issue.1, pp.76-105, 2006.
DOI : 10.1016/j.dam.2005.07.002

R. Hung and M. Chang, Finding a minimum path cover of a distance-hereditary graph in polynomial time, Discrete Applied Mathematics, vol.155, issue.17, pp.2242-2256, 2007.
DOI : 10.1016/j.dam.2007.06.001

S. Kundu, A linear algorithm for the hamiltonian completion number of a tree, Information Processing Letters, vol.5, issue.2, pp.55-57, 1976.
DOI : 10.1016/0020-0190(76)90080-6

V. Lehoux-lebacque, N. Brauner, and G. Finke, Identical coupled task scheduling: polynomial complexity of the cyclic case, Journal of Scheduling, vol.14, issue.5, 2009.
DOI : 10.1007/s10951-015-0438-9

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

S. Moran and Y. Wolfstahl, Optimal covering of cacti by vertex-disjoint paths, Theoretical Computer Science, vol.84, issue.2, pp.179-197, 1988.
DOI : 10.1016/0304-3975(91)90159-Y

URL : http://doi.org/10.1016/0304-3975(91)90159-y

K. Nakano, S. Olariu, and A. Y. Zomaya, A time-optimal solution for the path cover problem on cographs, Theoretical Computer Science, vol.290, issue.3, pp.1541-1556, 2003.
DOI : 10.1016/S0304-3975(02)00068-3

A. J. Orman and C. N. Potts, On the complexity of coupled-task scheduling, Discrete Applied Mathematics, vol.72, issue.1-2, pp.141-154, 1997.
DOI : 10.1016/S0166-218X(96)00041-8

A. Schrijver, Combinatorial Optimization : Polyhedra and Efficiency (Algorithms and Combinatorics), 2004.

R. D. Shapiro, Scheduling coupled tasks, Naval Research Logistics Quarterly, vol.12, issue.3, pp.477-481, 1980.
DOI : 10.1002/nav.3800270312

G. Simonin, Impact du graphe de compatibilité sur la complexité et l'approximation des problèmes d'ordonnancement en présence de tâches-couplées, 2009.

G. Simonin, R. Giroudeau, and J. König, Complexity and approximation for scheduling problem for a torpedo, CIE'39 : The 39th International Conference on Computers and Industrial Engineering, pp.300-304, 2009.
DOI : 10.1016/j.cie.2011.01.015

URL : https://hal.archives-ouvertes.fr/lirmm-00355052

G. Simonin, R. Giroudeau, and J. König, Extended matching problem for a coupled-tasks scheduling problem, TMFCS'09 : International Conference on Theoretical and Mathematical Foundations of Computer Science, pp.82-089, 2009.
URL : https://hal.archives-ouvertes.fr/lirmm-00375000

R. Srikant, R. Sundaram, K. S. Singh, and C. Pandu-rangan, Optimal path cover problem on block graphs and bipartite permutation graphs, Theoretical Computer Science, vol.115, issue.2, pp.351-357, 1993.
DOI : 10.1016/0304-3975(93)90123-B

URL : http://doi.org/10.1016/0304-3975(93)90123-b