{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T04:16:21Z","timestamp":1768709781815,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T00:00:00Z","timestamp":1629072000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T00:00:00Z","timestamp":1629072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"national natural science foundation of china","doi-asserted-by":"publisher","award":["11771114"],"award-info":[{"award-number":["11771114"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"national natural science foundation of china","doi-asserted-by":"publisher","award":["11971139"],"award-info":[{"award-number":["11971139"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004731","name":"natural science foundation of zhejiang province","doi-asserted-by":"publisher","award":["LY21A010014"],"award-info":[{"award-number":["LY21A010014"]}],"id":[{"id":"10.13039\/501100004731","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004543","name":"china scholarship council","doi-asserted-by":"publisher","award":["201508330054"],"award-info":[{"award-number":["201508330054"]}],"id":[{"id":"10.13039\/501100004543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004543","name":"china scholarship council","doi-asserted-by":"publisher","award":["201706315073"],"award-info":[{"award-number":["201706315073"]}],"id":[{"id":"10.13039\/501100004543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004543","name":"china scholarship council","doi-asserted-by":"publisher","award":["201908330090"],"award-info":[{"award-number":["201908330090"]}],"id":[{"id":"10.13039\/501100004543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012476","name":"fundamental research funds for central universities of the central south university","doi-asserted-by":"publisher","award":["20720160035"],"award-info":[{"award-number":["20720160035"]}],"id":[{"id":"10.13039\/501100012476","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s10878-021-00793-3","type":"journal-article","created":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T08:02:52Z","timestamp":1629100972000},"page":"571-588","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph"],"prefix":"10.1007","volume":"43","author":[{"given":"Yong","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yinhui","family":"Cai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Longcheng","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guangting","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Randy","family":"Goebel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4283-3396","authenticated-orcid":false,"given":"Guohui","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bing","family":"Su","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"An","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,16]]},"reference":[{"key":"793_CR1","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1002\/net.20200","volume":"50","author":"K Asdre","year":"2007","unstructured":"Asdre K, Nikolopoulos SD (2007) A linear-time algorithm for the $$k$$-fixed-endpoint path cover problem on cographs. Networks 50:231\u2013240","journal-title":"Networks"},{"key":"793_CR2","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1016\/j.tcs.2009.11.003","volume":"411","author":"K Asdre","year":"2010","unstructured":"Asdre K, Nikolopoulos SD (2010) A polynomial solution to the $$k$$-fixed-endpoint path cover problem on proper interval graphs. Theor Comput Sci 411:967\u2013975","journal-title":"Theor Comput Sci"},{"key":"793_CR3","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(96)00031-X","volume":"162","author":"BS Baker","year":"1996","unstructured":"Baker BS, Coffman EG (1996) Mutual exclusion scheduling. Theor Comput Sci 162:225\u2013243","journal-title":"Theor Comput Sci"},{"key":"793_CR4","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.cor.2011.04.014","volume":"39","author":"M Bendraouche","year":"2012","unstructured":"Bendraouche M, Boudhar M (2012) Scheduling jobs on identical machines with agreement graph. Comput Oper Res 39:382\u2013390","journal-title":"Comput Oper Res"},{"key":"793_CR5","doi-asserted-by":"publisher","first-page":"3508","DOI":"10.1080\/00207543.2015.1073860","volume":"54","author":"M Bendraouche","year":"2016","unstructured":"Bendraouche M, Boudhar M (2016) Scheduling with agreements: new results. Int J Prod Res 54:3508\u20133522","journal-title":"Int J Prod Res"},{"key":"793_CR6","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF02283747","volume":"16","author":"J B\u0142a\u017cewicz","year":"1988","unstructured":"B\u0142a\u017cewicz J, Kubiak W, Szwarcfiter J (1988) Scheduling unit - time tasks on flow - shops under resource constraints. Ann Oper Res 16:255\u2013266","journal-title":"Ann Oper Res"},{"key":"793_CR7","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(83)90012-4","volume":"5","author":"J Blazewicz","year":"1983","unstructured":"Blazewicz J, Lenstra JK, Rinnooy Kan AHG (1983) Scheduling subject to resource constraints: classification and complexity. Discret Appl Math 5:11\u201324","journal-title":"Discret Appl Math"},{"key":"793_CR8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0304-3975(95)00057-4","volume":"148","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender HL, Jansen K (1995) Restrictions of graph partition problems. Part I. Theor Comput Sci 148:93\u2013109","journal-title":"Theor Comput Sci"},{"key":"793_CR9","doi-asserted-by":"crossref","unstructured":"Cai Y, Chen G, Chen Y, Goebel R, Lin G, Liu L, Zhang A (2018) Approximation algorithms for two-machine flow-shop scheduling with a conflict graph. In: Proceedings of the 24th international computing and combinatorics conference (COCOON 2018), LNCS 10976, pp 205\u2013217","DOI":"10.1007\/978-3-319-94776-1_18"},{"key":"793_CR10","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1287\/opre.44.6.891","volume":"44","author":"B Chen","year":"1996","unstructured":"Chen B, Glass CA, Potts CN, Strusevich VA (1996) A new heuristic for three-machine flow shop scheduling. Oper Res 44:891\u2013898","journal-title":"Oper Res"},{"key":"793_CR11","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s10951-008-0089-1","volume":"12","author":"G Even","year":"2009","unstructured":"Even G, Halld\u00f3rsson MM, Kaplan L, Ron D (2009) Scheduling with conflicts: online and offline algorithms. J Schedul 12:199\u2013224","journal-title":"J Schedul"},{"key":"793_CR12","doi-asserted-by":"crossref","unstructured":"Gabow HN (1983) An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proceedings of the 15th annual ACM symposium on theory of computing (STOC\u201983), pp 448\u2013456","DOI":"10.1145\/800061.808776"},{"key":"793_CR13","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1137\/0204015","volume":"4","author":"MR Garey","year":"1975","unstructured":"Garey MR, Graham RL (1975) Bounds for multiprocessor scheduling with resource constraints. SIAM J Comput 4:187\u2013200","journal-title":"SIAM J Comput"},{"key":"793_CR14","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/0204035","volume":"4","author":"MR Garey","year":"1975","unstructured":"Garey MR, Johnson DS (1975) Complexity results for multiprocessor scheduling under resource constraints. SIAM J Comput 4:397\u2013411","journal-title":"SIAM J Comput"},{"key":"793_CR15","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco"},{"key":"793_CR16","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1287\/moor.1.2.117","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1:117\u2013129","journal-title":"Math Oper Res"},{"key":"793_CR17","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"MR Garey","year":"1976","unstructured":"Garey MR, Johnson DS, Tarjan RE (1976) The planar Hamiltonian circuit problem is NP-complete. SIAM J Comput 5:704\u2013714","journal-title":"SIAM J Comput"},{"key":"793_CR18","volume-title":"Algorithmic graph theory and perfect graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs. Elsevier, Amsterdam"},{"key":"793_CR19","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s10878-019-00488-w","volume":"39","author":"R G\u00f3mez","year":"2020","unstructured":"G\u00f3mez R, Wakabayashi Y (2020) Nontrivial path covers of graphs: existence, minimization and maximization. J Combin Optim 39:437\u2013456","journal-title":"J Combin Optim"},{"key":"793_CR20","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1287\/opre.26.1.36","volume":"26","author":"T Gonzalez","year":"1978","unstructured":"Gonzalez T, Sahni S (1978) Flowshop and jobshop schedules: complexity and approximation. Oper Res 26:36\u201352","journal-title":"Oper Res"},{"key":"793_CR21","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discret Math 5:287\u2013326","journal-title":"Ann Discret Math"},{"key":"793_CR22","first-page":"175","volume":"82","author":"LA Hall","year":"1998","unstructured":"Hall LA (1998) Approximability of flow shop scheduling. Math Program 82:175\u2013190","journal-title":"Math Program"},{"key":"793_CR23","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0890-5401(02)00032-9","volume":"180","author":"MM Halld\u00f3rsson","year":"2003","unstructured":"Halld\u00f3rsson MM, Kortsarz G, Proskurowski A, Salman R, Shachnai H, Telle JA (2003) Multicoloring trees. Inf Comput 180:113\u2013129","journal-title":"Inf Comput"},{"key":"793_CR24","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/nav.3800010110","volume":"1","author":"SM Johnson","year":"1954","unstructured":"Johnson SM (1954) Optimal two- and three-machine production schedules with setup times included. Naval Res Logist 1:61\u201368","journal-title":"Naval Res Logist"},{"key":"793_CR25","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0012-365X(95)00057-4","volume":"156","author":"H M\u00fcller","year":"1996","unstructured":"M\u00fcller H (1996) Hamiltonian circuits in chordal bipartite graphs. Discret Math 156:291\u2013298","journal-title":"Discret Math"},{"key":"793_CR26","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.ipl.2007.12.006","volume":"107","author":"LL Pao","year":"2008","unstructured":"Pao LL, Hong CH (2008) The two-equal-disjoint path cover problem of matching composition network. Inf Process Lett 107:18\u201323","journal-title":"Inf Process Lett"},{"key":"793_CR27","doi-asserted-by":"publisher","first-page":"S5","DOI":"10.1186\/1471-2105-15-S9-S5","volume":"15","author":"R Rizzi","year":"2014","unstructured":"Rizzi R, Tomescu AI, M\u00e4kinen V (2014) On the complexity of minimum path cover with subpath constraints for multi-assembly. BMC Bioinform 15:S5","journal-title":"BMC Bioinform"},{"key":"793_CR28","unstructured":"R\u00f6ck H (1983) Scheduling unit task shops with resource constraints and excess usage costs. Technical Report, Fachbereich Informatik, Technical University of Berlin, Berlin"},{"key":"793_CR29","first-page":"1","volume":"28","author":"H R\u00f6ck","year":"1984","unstructured":"R\u00f6ck H (1984) Some new results in flow shop scheduling. Zeitschrift f\u00fcr Oper Res 28:1\u201316","journal-title":"Zeitschrift f\u00fcr Oper Res"},{"key":"793_CR30","first-page":"497","volume":"36","author":"H S\u00fcral","year":"1992","unstructured":"S\u00fcral H, Kondakci S, Erkip N (1992) Scheduling unit-time tasks in renewable resource constrained flowshops. Zeitschrift f\u00fcr Oper Res 36:497\u2013516","journal-title":"Zeitschrift f\u00fcr Oper Res"},{"key":"793_CR31","doi-asserted-by":"publisher","first-page":"1664","DOI":"10.1080\/00207543.2016.1206672","volume":"55","author":"NEH Tellache","year":"2017","unstructured":"Tellache NEH, Boudhar M (2017) Two-machine flow shop problem with unit-time operations and conflict graph. Int J Prod Res 55:1664\u20131679","journal-title":"Int J Prod Res"},{"key":"793_CR32","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/s10479-017-2560-x","volume":"261","author":"NEH Tellache","year":"2018","unstructured":"Tellache NEH, Boudhar M (2018) Flow shop scheduling problem with conflict graphs. Ann Oper Res 261:339\u2013363","journal-title":"Ann Oper Res"},{"key":"793_CR33","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1287\/opre.45.2.288","volume":"45","author":"DP Williamson","year":"1997","unstructured":"Williamson DP, Hall LA, Hoogeveen JA, Hurkens CAJ, Lenstra JK, Sevastianov SV, Shmoys DB (1997) Short shop schedules. Oper Res 45:288\u2013294","journal-title":"Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00793-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00793-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00793-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T21:06:03Z","timestamp":1648587963000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00793-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,16]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["793"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00793-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,16]]},"assertion":[{"value":"2 August 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 August 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}