{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:24:39Z","timestamp":1759847079516},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2010,9,16]],"date-time":"2010-09-16T00:00:00Z","timestamp":1284595200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2011,10]]},"DOI":"10.1007\/s10951-010-0193-x","type":"journal-article","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T14:57:48Z","timestamp":1284562668000},"page":"501-509","source":"Crossref","is-referenced-by-count":12,"title":["Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor"],"prefix":"10.1007","volume":"14","author":[{"given":"G.","family":"Simonin","sequence":"first","affiliation":[]},{"given":"B.","family":"Darties","sequence":"additional","affiliation":[]},{"given":"R.","family":"Giroudeau","sequence":"additional","affiliation":[]},{"given":"J.-C.","family":"K\u00f6nig","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,9,16]]},"reference":[{"issue":"11","key":"193_CR1","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s001860300328","volume":"59","author":"D. Ahr","year":"2004","unstructured":"Ahr, D., B\u00e9k\u00e9si, J., Galambos, G., Oswald, M., & Reinelt, G. (2004). An exact algorithm for scheduling identical coupled-tasks. Mathematical Methods of Operations Research, 59(11), 193\u2013203.","journal-title":"Mathematical Methods of Operations Research"},{"issue":"3","key":"193_CR2","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0020-0190(90)90064-5","volume":"35","author":"R. S. Arikati","year":"1990","unstructured":"Arikati, R. S., & Rangan, P. C. (1990). Linear algorithm for optimal path cover problem on interval graphs. Information Processing Letters, 35(3), 149\u2013153.","journal-title":"Information Processing Letters"},{"key":"193_CR3","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1145\/1109557.1109627","volume-title":"SODA \u201906: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm","author":"P. Berman","year":"2006","unstructured":"Berman, P., & Karpinski, M. (2006). 8\/7-approximation algorithm for (1,2)-TSP. In SODA \u201906: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (pp. 641\u2013648). New York: ACM."},{"key":"193_CR4","unstructured":"Bla\u017cewicz, J., Ecker, K., Kis, T., Potts, C. N., Tanas, M., & Whitehead, J. (2009). Scheduling of coupled tasks with unit processing times. Technical report, Poznan University of Technology."},{"key":"193_CR5","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BFb0066442","volume":"406","author":"F. T. Boesch","year":"1974","unstructured":"Boesch, F. T., Chen, S., & McHugh, B. (1974). On covering the points of a graph with point-disjoint paths. Graphs and Combinatorics, 406, 201\u2013212.","journal-title":"Graphs and Combinatorics"},{"key":"193_CR6","first-page":"641","volume-title":"Scheduling theory and its applications","author":"Ph. Chr\u00e9tienne","year":"1995","unstructured":"Chr\u00e9tienne, Ph., & Picouleau, C. (1995). Scheduling with communication delays: a survey. In Scheduling theory and its applications (pp. 641\u2013648). New York: Wiley."},{"issue":"2\u20133","key":"193_CR7","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/S0166-218X(03)00441-4","volume":"136","author":"P. Detti","year":"2004","unstructured":"Detti, P., & Meloni, C. (2004). A linear algorithm for the hamiltonian completion number of the line graph of a cactus. Discrete Applied Mathematics, 136(2\u20133), 197\u2013215.","journal-title":"Discrete Applied Mathematics"},{"key":"193_CR8","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York: Freeman."},{"issue":"3","key":"193_CR9","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1145\/321892.321897","volume":"22","author":"S. E. Goodman","year":"1975","unstructured":"Goodman, S. E., Hedetniemi, S. T., & Slater, P. J. (1975). Advances on the hamiltonian completion problem. Journal of the ACM, 22(3), 352\u2013360.","journal-title":"Journal of the ACM"},{"key":"193_CR10","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R. L. Graham","year":"1979","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287\u2013326.","journal-title":"Annals of Discrete Mathematics"},{"issue":"1","key":"193_CR11","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/j.dam.2005.07.002","volume":"154","author":"R.-W. Hung","year":"2006","unstructured":"Hung, R.-W., & Chang, M.-S. (2006). Solving the path cover problem on circular-arc graphs by using an approximation algorithm. Discrete Applied Mathematics, 154(1), 76\u2013105.","journal-title":"Discrete Applied Mathematics"},{"issue":"17","key":"193_CR12","doi-asserted-by":"crossref","first-page":"2242","DOI":"10.1016\/j.dam.2007.06.001","volume":"155","author":"R.-W. Hung","year":"2007","unstructured":"Hung, R.-W., & Chang, M.-S. (2007). Finding a minimum path cover of a distance-hereditary graph in polynomial time. Discrete Applied Mathematics, 155(17), 2242\u20132256.","journal-title":"Discrete Applied Mathematics"},{"key":"193_CR13","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0020-0190(76)90080-6","volume":"5","author":"S. Kundu","year":"1976","unstructured":"Kundu, S. (1976). A linear algorithm for the hamiltonian completion number of a tree. Information Processing Letters, 5, 55\u201357.","journal-title":"Information Processing Letters"},{"key":"193_CR14","unstructured":"Lehoux-Lebacque, V., Brauner, N., & Finke, G. (2009). Identical coupled task scheduling: polynomial complexity of the cyclic case. Les Cahiers Leibniz, 179."},{"key":"193_CR15","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0304-3975(91)90159-Y","volume":"84","author":"S. Moran","year":"1988","unstructured":"Moran, S., & Wolfstahl, Y. (1988). Optimal covering of cacti by vertex-disjoint paths. Theoretical Computer Science, 84, 179\u2013197.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"193_CR16","doi-asserted-by":"crossref","first-page":"1541","DOI":"10.1016\/S0304-3975(02)00068-3","volume":"290","author":"K. Nakano","year":"2003","unstructured":"Nakano, K., Olariu, S., & Zomaya, A. Y. (2003). A time-optimal solution for the path cover problem on cographs. Theoretical Computer Science, 290(3), 1541\u20131556.","journal-title":"Theoretical Computer Science"},{"key":"193_CR17","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/S0166-218X(96)00041-8","volume":"72","author":"A. J. Orman","year":"1997","unstructured":"Orman, A. J., & Potts, C. N. (1997). On the complexity of coupled-task scheduling. Discrete Applied Mathematics, 72, 141\u2013154.","journal-title":"Discrete Applied Mathematics"},{"key":"193_CR18","volume-title":"Combinatorial optimization: polyhedra and efficiency (algorithms and combinatorics)","author":"A. Schrijver","year":"2004","unstructured":"Schrijver, A. (2004). Combinatorial optimization: polyhedra and efficiency (algorithms and combinatorics). Berlin: Springer."},{"key":"193_CR19","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1002\/nav.3800270311","volume":"27","author":"R. D. Shapiro","year":"1980","unstructured":"Shapiro, R. D. (1980). Scheduling coupled tasks. Naval Research Logistics Quarterly, 27, 477\u2013481.","journal-title":"Naval Research Logistics Quarterly"},{"key":"193_CR20","unstructured":"Simonin, G. (2009). Impact du graphe de compatibilit\u00e9 sur la complexit\u00e9 et l\u2019approximation des probl\u00e8mes d\u2019ordonnancement en pr\u00e9sence de t\u00e2ches-coupl\u00e9es. Ph.D thesis, LIRMM, December 2009."},{"key":"193_CR21","doi-asserted-by":"crossref","unstructured":"Simonin, G., Giroudeau, R., & K\u00f6nig, J.-C. (2009a). Complexity and approximation for scheduling problem for a torpedo. In CIE\u201939: The 39th international conference on computers and industrial engineering, IEEE, Troyes, France (pp. 300\u2013304).","DOI":"10.1109\/ICCIE.2009.5223825"},{"key":"193_CR22","unstructured":"Simonin, G., Giroudeau, R., & K\u00f6nig, J.-C. (2009b). Extended matching problem for a coupled-tasks scheduling problem. In TMFCS\u201909: international conference on theoretical and mathematical foundations of computer science, Orlando, Florida (pp. 082\u2013089)."},{"issue":"2","key":"193_CR23","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/0304-3975(93)90123-B","volume":"115","author":"R. Srikant","year":"1993","unstructured":"Srikant, R., Sundaram, R., Sher Singh, K., & Rangan, P. C. (1993). Optimal path cover problem on block graphs and bipartite permutation graphs. Theoretical Computer Science, 115(2), 351\u2013357.","journal-title":"Theoretical Computer Science"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-010-0193-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-010-0193-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-010-0193-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T20:08:55Z","timestamp":1559678935000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-010-0193-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,16]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["193"],"URL":"https:\/\/doi.org\/10.1007\/s10951-010-0193-x","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9,16]]}}}