{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:44:47Z","timestamp":1740141887802,"version":"3.37.3"},"reference-count":66,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,11,5]],"date-time":"2022-11-05T00:00:00Z","timestamp":1667606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,11,5]],"date-time":"2022-11-05T00:00:00Z","timestamp":1667606400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["4OR-Q J Oper Res"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s10288-022-00525-1","type":"journal-article","created":{"date-parts":[[2022,11,5]],"date-time":"2022-11-05T15:04:46Z","timestamp":1667660686000},"page":"533-566","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Moderate exponential-time algorithms for scheduling problems"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7440-2980","authenticated-orcid":false,"given":"Vincent","family":"T\u2019kindt","sequence":"first","affiliation":[]},{"given":"Federico","family":"Della Croce","sequence":"additional","affiliation":[]},{"given":"Mathieu","family":"Liedloff","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,5]]},"reference":[{"key":"525_CR1","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s10951-018-0581-1","volume":"22","author":"S Bessy","year":"2020","unstructured":"Bessy S, Giroudeau R (2020) Parameterized complexity of a coupled-task scheduling problem. J Sched 22:305\u2013313. https:\/\/doi.org\/10.1007\/s10951-018-0581-1","journal-title":"J Sched"},{"issue":"1","key":"525_CR2","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1109\/FOCS.2010.24","volume":"43","author":"A Bj\u00f6rklund","year":"2014","unstructured":"Bj\u00f6rklund A (2014) Determinant sums for undirected hamiltonicity. SIAM J Comput 43(1):280\u2013299. https:\/\/doi.org\/10.1109\/FOCS.2010.24","journal-title":"SIAM J Comput"},{"key":"525_CR3","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund A, Husfeldt T, Kaski P, et\u00a0al (2008) The traveling salesman problem in bounded degree graphs. In: Aceto L, Damgard I, Goldberg L, et\u00a0al (eds) Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. Springer, vol 5125, p 198\u2013209","DOI":"10.1007\/978-3-540-70575-8_17"},{"issue":"2","key":"525_CR4","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"36","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund A, Husfeldt T, Koivisto M (2009) Set partitioning via Inclusion-Exclusion. SIAM J Comput 36(2):546\u2013563. https:\/\/doi.org\/10.1137\/070683933","journal-title":"SIAM J Comput"},{"key":"525_CR5","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/s00453-014-9889-1","volume":"71","author":"E Bonnet","year":"2015","unstructured":"Bonnet E, Escoffier B, Kim E et al (2015) On subexponential and FPT-time inapproximability. Algorithmica 71:541\u2013565. https:\/\/doi.org\/10.1007\/s00453-014-9889-1","journal-title":"Algorithmica"},{"key":"525_CR6","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.jcss.2017.09.009","volume":"92","author":"E Bonnet","year":"2018","unstructured":"Bonnet E, Lampis M, Paschos V (2018) Time-approximation trade-offs for inapproximable problems. J Comput Syst Sci 92:171\u2013180. https:\/\/doi.org\/10.1016\/j.jcss.2017.09.009","journal-title":"J Comput Syst Sci"},{"key":"525_CR7","volume-title":"Scheduling algorithms","author":"P Brucker","year":"2007","unstructured":"Brucker P (2007) Scheduling algorithms. Springer"},{"key":"525_CR8","doi-asserted-by":"publisher","unstructured":"Cygan M, Pilipczuk M, Pilipczuk M, et\u00a0al (2011) Scheduling partially ordered jobs faster than $$2^n$$. In: C. Demetrescu and M.M. Halldorsson (Eds): Proceedings of 19th Annual European Symposium (ESA 2011), Lecture Notes in Computer Science, vol 6942, pp 299\u2013310, https:\/\/doi.org\/10.1007\/978-3-642-23719-5_26","DOI":"10.1007\/978-3-642-23719-5_26"},{"key":"525_CR9","doi-asserted-by":"publisher","unstructured":"Cygan M, Fomin FV, Kowalik \u0141, et\u00a0al (2015) Lower bounds based on the exponential-time hypothesis, Springer International Publishing, Cham, pp 467\u2013521. https:\/\/doi.org\/10.1007\/978-3-319-21275-3_14","DOI":"10.1007\/978-3-319-21275-3_14"},{"key":"525_CR10","doi-asserted-by":"publisher","DOI":"10.1145\/2925416","author":"M Cygan","year":"2016","unstructured":"Cygan M, Dell H, Lokshtanov D et al (2016) On problems as hard as CNF-SAT. ACM Trans Algorithms. https:\/\/doi.org\/10.1145\/2925416","journal-title":"ACM Trans Algorithms"},{"key":"525_CR11","unstructured":"Da\u00a0Silva D (1854) General properties and direct resolution of binomial congruences. Real Academia das Ciencias de Lisboa"},{"key":"525_CR12","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M Davis","year":"1960","unstructured":"Davis M, Putnam H (1960) A computing procedure for quantification theory. J ACM 7:201\u2013215. https:\/\/doi.org\/10.1145\/321033.321034","journal-title":"J ACM"},{"key":"525_CR13","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M Davis","year":"1962","unstructured":"Davis M, Logemann G, Loveland D (1962) A machine program for theorem-proving. Commun ACM 5:394\u2013397. https:\/\/doi.org\/10.1145\/368273.368557","journal-title":"Commun ACM"},{"issue":"2","key":"525_CR14","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1016\/j.ejor.2020.09.042","volume":"291","author":"M de Weerdt","year":"2021","unstructured":"de Weerdt M, Baart R, He L (2021) Single-machine scheduling with release times, deadlines, setup times, and rejection. Eur J Oper Res 291(2):629\u2013639. https:\/\/doi.org\/10.1016\/j.ejor.2020.09.042","journal-title":"Eur J Oper Res"},{"key":"525_CR15","doi-asserted-by":"publisher","unstructured":"Della Croce F, T\u2019kindt V, Ploton O, (2021) Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms. Appl Math Comput. https:\/\/doi.org\/10.1016\/j.amc.2020.125888","DOI":"10.1016\/j.amc.2020.125888"},{"key":"525_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R Downey","year":"1999","unstructured":"Downey R, Fellows M (1999) Parameterized complexity. Springer"},{"key":"525_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact exponential algorithms","author":"F Fomin","year":"2010","unstructured":"Fomin F, Kratsch D (2010) Exact exponential algorithms. Springer"},{"issue":"5","key":"525_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"F Fomin","year":"2009","unstructured":"Fomin F, Grandoni F, Kratsch D (2009) A measure & conquer approach for the analysis of exact algorithms. J ACM 56(5):1\u201332. https:\/\/doi.org\/10.1145\/1552285.1552286","journal-title":"J ACM"},{"key":"525_CR19","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco (USA)"},{"key":"525_CR20","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.tcs.2018.05.040","volume":"745","author":"M Garraffa","year":"2018","unstructured":"Garraffa M, Shang L, Della Croce F et al (2018) An exact exponential branch-and-merge algorithm for the single machine total tardiness problem. Theoret Comput Sci 745:133\u2013149. https:\/\/doi.org\/10.1016\/j.tcs.2018.05.040","journal-title":"Theoret Comput Sci"},{"key":"525_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 et al (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287\u2013326. https:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X","journal-title":"Ann Discrete Math"},{"issue":"1\u20132","key":"525_CR22","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BF01585870","volume":"82","author":"L Hall","year":"1998","unstructured":"Hall L (1998) Approximability of flow shop scheduling. Math Program, series B 82(1\u20132):175\u2013190. https:\/\/doi.org\/10.1007\/BF01585870","journal-title":"Math Program, series B"},{"key":"525_CR23","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10479-018-2852-9","volume":"298","author":"D Hermelin","year":"2021","unstructured":"Hermelin D, Karhi S, Pinedo M et al (2021) New algorithms for minimizing the weighted number of tardy jobs on a single machine. Ann Oper Res 298:271\u2013287. https:\/\/doi.org\/10.1007\/s10479-018-2852-9","journal-title":"Ann Oper Res"},{"issue":"2","key":"525_CR24","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/120868177","volume":"43","author":"T Hertli","year":"2014","unstructured":"Hertli T (2014) 3-SAT faster and simpler-Unique-SAT bounds for PPSZ hold in general. SIAM J Comput 43(2):718\u2013729. https:\/\/doi.org\/10.1137\/120868177","journal-title":"SIAM J Comput"},{"issue":"2","key":"525_CR25","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E Horowitz","year":"1974","unstructured":"Horowitz E, Sahni S (1974) Computing partitions with applications to the knapsack problem. J ACM 21(2):277\u2013292. https:\/\/doi.org\/10.1145\/321812.321823","journal-title":"J ACM"},{"issue":"2","key":"525_CR26","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R (2001) On the complexity of k-SAT. J Comput Syst Sci 62(2):367\u2013375. https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"525_CR27","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J Comput Syst Sci 63(4):512\u2013530. https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J Comput Syst Sci"},{"key":"#cr-split#-525_CR28.1","unstructured":"Iwama K, Nakashima T (2007) An improved exact algorithm for cubic graph TSP. In: Lin G"},{"key":"#cr-split#-525_CR28.2","unstructured":"(ed) Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings. Springer, vol 4598, p 108-117"},{"issue":"2","key":"525_CR29","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1137\/S0895480199363908","volume":"16","author":"K Jansen","year":"2003","unstructured":"Jansen K, Solis-Oba R, Sviridenko M (2003) Makespan minimization in job shops: a linear time approximation scheme. SIAM J Discret Math 16(2):288\u2013300. https:\/\/doi.org\/10.1137\/S0895480199363908","journal-title":"SIAM J Discret Math"},{"key":"525_CR30","unstructured":"Jansen K, Land F, Land K (2013) Bounding the running time of algorithms for scheduling and packing problems. In: Dehne F, Solis-Oba R, Sack JR (eds) Algorithms and Data Structures - 13th International Symposium. Springer, vol 8037, p 281\u2013290"},{"issue":"1","key":"525_CR31","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/nav.3800010110","volume":"1","author":"S Johnson","year":"1954","unstructured":"Johnson S (1954) Optimal two- and three-stage production schedules with setup times included. Naval Res Logist Q 1(1):61\u201368. https:\/\/doi.org\/10.1002\/nav.3800010110","journal-title":"Naval Res Logist Q"},{"issue":"2","key":"525_CR32","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0167-6377(82)90044-X","volume":"1","author":"R Karp","year":"1982","unstructured":"Karp R (1982) Dynamic programming meets the principle of inclusion and exclusion. Oper Res Lett 1(2):49\u201351. https:\/\/doi.org\/10.1016\/0167-6377(82)90044-X","journal-title":"Oper Res Lett"},{"key":"525_CR33","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s10951-017-0550-0","volume":"21","author":"D Knop","year":"2018","unstructured":"Knop D, Koutecky M (2018) Scheduling meets $$n$$-fold integer programming. J Sched 21:493\u2013503. https:\/\/doi.org\/10.1007\/s10951-017-0550-0","journal-title":"J Sched"},{"key":"525_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-019-01402-2","volume":"184","author":"D Knop","year":"2020","unstructured":"Knop D, Koutecky M, Mnich M (2020) Combinatorial $$n$$-fold integer programming and applications. Math Program 184:1\u201334. https:\/\/doi.org\/10.1007\/s10107-019-01402-2","journal-title":"Math Program"},{"key":"525_CR35","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","volume":"5","author":"E Lawler","year":"1976","unstructured":"Lawler E (1976) A note on the complexity of the chromatic number problem. Inf Process Lett 5:66\u201367. https:\/\/doi.org\/10.1016\/0020-0190(76)90065-X","journal-title":"Inf Process Lett"},{"key":"525_CR36","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/S0167-5060(08)70742-8","volume":"1","author":"E Lawler","year":"1977","unstructured":"Lawler E (1977) A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Ann Discrete Math 1:331\u2013342. https:\/\/doi.org\/10.1016\/S0167-5060(08)70742-8","journal-title":"Ann Discrete Math"},{"key":"525_CR37","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2013.05.023","volume":"511","author":"C Lente","year":"2013","unstructured":"Lente C, Liedloff M, Soukhal A et al (2013) On an extension of the Sort & Search method with application to scheduling theory. Theoret Comput Sci 511:13\u201322. https:\/\/doi.org\/10.1016\/j.tcs.2013.05.023","journal-title":"Theoret Comput Sci"},{"key":"525_CR38","unstructured":"Lente C, Liedloff M, Soukhal A, et\u00a0al (2014) Exponential algorithms for scheduling problems. HAL https:\/\/hal.archives-ouvertes.fr\/hal-00944382"},{"issue":"1","key":"525_CR39","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D Marx","year":"2008","unstructured":"Marx D (2008) Parameterized complexity and approximation algorithms. Comput J 51(1):60\u201378. https:\/\/doi.org\/10.1093\/comjnl\/bxm048","journal-title":"Comput J"},{"key":"525_CR40","unstructured":"Marx D (2011) Fixed-parameter tractable scheduling problems. In: K. Jansen, C. Mathieu, H. Shachnai, and N.E. Young (Eds): Packing and scheduling algorithms for information and communication services, Dagstuhl Rep, 1(2), p\u00a086"},{"key":"525_CR41","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/j.cor.2018.07.020","volume":"100","author":"M Mnich","year":"2018","unstructured":"Mnich M, van Bevern R (2018) Parameterized complexity of machine scheduling: 15 open problems. Comput Oper Res 100:254\u2013261. https:\/\/doi.org\/10.1016\/j.cor.2018.07.020","journal-title":"Comput Oper Res"},{"key":"525_CR42","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s10107-014-0830-9","volume":"154","author":"M Mnich","year":"2015","unstructured":"Mnich M, Wiese A (2015) Scheduling and fixed-parameter tractability. Math Program 154:533\u2013562. https:\/\/doi.org\/10.1007\/s10107-014-0830-9","journal-title":"Math Program"},{"key":"525_CR43","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2020.11.024","volume":"290","author":"A Munier","year":"2021","unstructured":"Munier A (2021) A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows. Discret Appl Math 290:1\u20136. https:\/\/doi.org\/10.1016\/j.dam.2020.11.024","journal-title":"Discret Appl Math"},{"key":"525_CR44","unstructured":"Nederlof J, Swennenhuis CMF (2020) On the Fine-Grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan. In: Cao Y, Pilipczuk M (eds) 15th International symposium on parameterized and exact computation (IPEC 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol 180. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, pp 25:1\u201325:17"},{"key":"525_CR45","doi-asserted-by":"publisher","unstructured":"Nederlof J, Wegrzycki K (2021) Improving Schroeppel and Shamir\u2019s algorithm for subset sum via orthogonal vectors. In: proceedings of the 53rd annual ACM sigact symposium on theory of computing. Association for Computing Machinery, New York, NY, USA, STOC 2021, p 1670-1683, https:\/\/doi.org\/10.1145\/3406325.3451024","DOI":"10.1145\/3406325.3451024"},{"key":"525_CR46","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier R (2006) Invitation to fixed-parameter algorithms. Oxford University Press"},{"key":"525_CR47","doi-asserted-by":"publisher","unstructured":"Paschos V (2015) When polynomial approximation meets exact computation. 4OR 13(3):227\u2013245. https:\/\/doi.org\/10.1007\/s10288-015-0294-7","DOI":"10.1007\/s10288-015-0294-7"},{"key":"525_CR48","volume-title":"Scheduling - theory, algorithms, and systems","author":"M Pinedo","year":"2016","unstructured":"Pinedo M (2016) Scheduling - theory, algorithms, and systems. Springer"},{"key":"525_CR49","doi-asserted-by":"crossref","unstructured":"Ploton O (2022) Contribution of inclusion-exclusion to exact or approximate solution of scheduling problems. PhD thesis, University of Tours","DOI":"10.1007\/s10288-023-00534-8"},{"key":"525_CR50","doi-asserted-by":"publisher","unstructured":"Ploton O, T\u2019kindt V, (2022a) Exponential-time algorithms for parallel machine scheduling problems. J Combinatorial Optim. https:\/\/doi.org\/10.1007\/s10878-022-00901-x","DOI":"10.1007\/s10878-022-00901-x"},{"key":"525_CR51","doi-asserted-by":"crossref","unstructured":"Ploton O, T\u2019kindt V (2022b) Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using inclusion-exclusion. Journal of Scheduling, to appear","DOI":"10.1007\/s10951-022-00759-1"},{"issue":"3","key":"525_CR52","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1287\/opre.26.3.444","volume":"26","author":"L Schrage","year":"1978","unstructured":"Schrage L, Baker KR (1978) Dynamic programming solution of sequencing problems with precedence constraints. Oper Res 26(3):444\u2013449","journal-title":"Oper Res"},{"issue":"3","key":"525_CR53","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/0210033","volume":"10","author":"R Schroeppel","year":"1981","unstructured":"Schroeppel R, Shamir A (1981) A $${T}={O}(2^\\frac{n}{2})$$, $${S}={O}(2^\\frac{n}{4})$$ algorithm for certain NP-complete problems. SIAM J Comput 10(3):456\u2013464. https:\/\/doi.org\/10.1137\/0210033","journal-title":"SIAM J Comput"},{"issue":"1\u20132","key":"525_CR54","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01585871","volume":"82","author":"S Sevastianov","year":"1998","unstructured":"Sevastianov S, Woeginger G (1998) Makespan minimization in open shops: a polynomial time approximation scheme. Math Program 82(1\u20132):191\u2013198. https:\/\/doi.org\/10.1007\/BF01585871","journal-title":"Math Program"},{"key":"525_CR55","doi-asserted-by":"publisher","unstructured":"Shang L, T\u2019kindt V, (2019) A Sort & Search method for multicriteria optimization problems with applications to scheduling theory. J Multi-Criteria Decis Anal 26(1\u20132):84\u201390. https:\/\/doi.org\/10.1002\/mcda.1660","DOI":"10.1002\/mcda.1660"},{"issue":"2","key":"525_CR56","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s10951-017-0524-2","volume":"21","author":"L Shang","year":"2018","unstructured":"Shang L, Lent\u00e9 C, Liedloff M et al (2018) Exact exponential algorithms for 3-machines flowshop scheduling problems. J Sched 21(2):227\u2013233. https:\/\/doi.org\/10.1007\/s10951-017-0524-2","journal-title":"J Sched"},{"key":"525_CR57","doi-asserted-by":"publisher","unstructured":"Shang L, T\u2019kindt V, Della Croce F, (2021) Branch & Memorize exact algorithms for sequencing problems: efficient embedding of memorization into search trees. Comput Oper Res 128. https:\/\/doi.org\/10.1016\/j.cor.2020.105171","DOI":"10.1016\/j.cor.2020.105171"},{"issue":"5","key":"525_CR58","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0167-6377(96)00031-4","volume":"19","author":"W Szwarc","year":"1996","unstructured":"Szwarc W, Mukhopadhyay S (1996) Decomposition of the single machine total tardiness problem. Oper Res Lett 19(5):243\u2013250. https:\/\/doi.org\/10.1016\/S0167-6377(96)00031-4","journal-title":"Oper Res Lett"},{"issue":"3","key":"525_CR59","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"R Tarjan","year":"1977","unstructured":"Tarjan R, Trojanowski A (1977) Finding a maximum independent set. SIAM J Comput 6(3):537\u2013546. https:\/\/doi.org\/10.1137\/0206038","journal-title":"SIAM J Comput"},{"key":"525_CR60","unstructured":"T\u2019kindt V, Billaut JC (2006) Multicriteria scheduling: Theory, models and algorithms. Springer, 2rd edition"},{"key":"525_CR61","doi-asserted-by":"publisher","unstructured":"T\u2019kindt V, Della Croce F, Bouquard JL, (2007) Enumeration of Pareto optima for a flowshop scheduling problem with two criteria. INFORMS J Comput 19(1):64\u201372. https:\/\/doi.org\/10.1287\/ijoc.1050.0167","DOI":"10.1287\/ijoc.1050.0167"},{"key":"525_CR62","doi-asserted-by":"publisher","unstructured":"T\u2019kindt V, Shang L, Della Croce F (2020) Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights. J Combinatorial Optim 39:764\u2013775. https:\/\/doi.org\/10.1007\/s10878-019-00512-z","DOI":"10.1007\/s10878-019-00512-z"},{"issue":"2003","key":"525_CR63","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume":"2570","author":"G Woeginger","year":"2003","unstructured":"Woeginger G (2003) Exact algorithms for NP-hard problems: A survey. Lect Notes Comput Sci 2570(2003):185\u2013207. https:\/\/doi.org\/10.1007\/3-540-36478-1_17","journal-title":"Lect Notes Comput Sci"},{"key":"525_CR64","doi-asserted-by":"crossref","unstructured":"Woeginger G (2004) Space and time complexity of exact algorithms: Some open problems. In: Downey R, Fellows M, Dehne F (eds) Parameterized and Exact Computation - 1st International Workshop, IWPEC 2004, Proceedings. Springer, vol 3162, p 281\u2013290","DOI":"10.1007\/978-3-540-28639-4_25"},{"issue":"1","key":"525_CR65","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.ic.2017.06.001","volume":"255","author":"M Xiao","year":"2017","unstructured":"Xiao M, Nagamochi H (2017) Exact algorithms for maximum independent set. Inf Comput 255(1):126\u2013146. https:\/\/doi.org\/10.1016\/j.ic.2017.06.001","journal-title":"Inf Comput"}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-022-00525-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10288-022-00525-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-022-00525-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,11]],"date-time":"2023-03-11T06:44:10Z","timestamp":1678517050000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10288-022-00525-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,5]]},"references-count":66,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["525"],"URL":"https:\/\/doi.org\/10.1007\/s10288-022-00525-1","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"type":"print","value":"1619-4500"},{"type":"electronic","value":"1614-2411"}],"subject":[],"published":{"date-parts":[[2022,11,5]]},"assertion":[{"value":"15 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 October 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}