{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:59:11Z","timestamp":1780783151220,"version":"3.54.1"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032277312","type":"print"},{"value":"9783032277329","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-27732-9_11","type":"book-chapter","created":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:35Z","timestamp":1780780475000},"page":"146-160","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Parameterized Complexity of\u00a0Scheduling with\u00a0Precedence Delays: Shuffle Product and\u00a0Directed Bandwidth"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9297-3330","authenticated-orcid":false,"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5654-1090","authenticated-orcid":false,"given":"Maher","family":"Mallem","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,7]]},"reference":[{"key":"11_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-319-44914-2_9","volume-title":"Discrete Optimization and Operations Research","author":"R van Bevern","year":"2016","unstructured":"van Bevern, R., Bredereck, R., Bulteau, L., Komusiewicz, C., Talmon, N., Woeginger, G.J.: Precedence-constrained scheduling problems parameterized by partial order width. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 105\u2013120. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-44914-2_9"},{"key":"11_CR2","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L.: Parameterized complexity of Bandwidth of caterpillars and Weighted Path Emulation. In: Kowalik, L., Pilipczuk, M., Rzazewski, P. (eds.) WG 2021. LNCS, vol. 12911, pp. 15\u201327. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-86838-3_2","DOI":"10.1007\/978-3-030-86838-3_2"},{"key":"11_CR3","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Groenland, C., Jacob, H., Jaffke, L., Lima, P.T.: XNLP-completeness for parameterized problems on graphs with a linear structure. In: Dell, H., Nederlof, J. (eds.) 17th International Symposium on Parameterized and Exact Computation, IPEC 2022. LIPIcs, vol.\u00a0249, pp. 8:1\u20138:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2022.8","DOI":"10.4230\/LIPIcs.IPEC.2022.8"},{"key":"11_CR4","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Groenland, C., Jacob, H., Pilipczuk, M., Pilipczuk, M.: On the complexity of problems on tree-structured graphs. In: Dell, H., Nederlof, J. (eds.) 17th International Symposium on Parameterized and Exact Computation, IPEC 2022. LIPIcs, vol.\u00a0249, pp. 6:1\u20136:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2022.6","DOI":"10.4230\/LIPIcs.IPEC.2022.6"},{"key":"11_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/J.IC.2024.105195","volume":"300","author":"HL Bodlaender","year":"2024","unstructured":"Bodlaender, H.L., Groenland, C., Nederlof, J., Swennenhuis, C.M.F.: Parameterized problems complete for nondeterministic FPT time and logarithmic space. Inf. Comput. 300, 105195 (2024). https:\/\/doi.org\/10.1016\/J.IC.2024.105195","journal-title":"Inf. Comput."},{"key":"11_CR6","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Hermelin, D., van Leeuwen, E.J.: Concurrency constrained scheduling with tree-like constraints. In: Fernau, H., Kindermann, P. (eds.) Proceedings 51th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2025. Lecture Notes in Computer Science, pp. 105\u2013120. Springer (2025). https:\/\/doi.org\/10.1007\/978-3-032-11835-6_8","DOI":"10.1007\/978-3-032-11835-6_8"},{"key":"11_CR7","unstructured":"Bodlaender, H.L., Mallem, M.: The parameterized complexity of scheduling with precedence delays: shuffle product and directed bandwidth (2026). https:\/\/arxiv.org\/abs\/2605.03727"},{"key":"11_CR8","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., van\u00a0der Wegen, M.: Parameterized complexity of scheduling chains of jobs with delays. In: Cao, Y., Pilipczuk, M. (eds.) 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, pp. 4:1\u20134:15. LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPICS.IPEC.2020.4, full version: https:\/\/arxiv.org\/abs\/2007.09023","DOI":"10.4230\/LIPICS.IPEC.2020.4"},{"key":"11_CR9","doi-asserted-by":"publisher","unstructured":"Bruno, Jones, So, K.: Deterministic scheduling with pipelined processors. IEEE Trans. Comput. C-29(4), 308\u2013316 (1980). https:\/\/doi.org\/10.1109\/TC.1980.1675569","DOI":"10.1109\/TC.1980.1675569"},{"issue":"2","key":"11_CR10","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0377-2217(96)00126-9","volume":"94","author":"J B\u0142a\u017cwicz","year":"1996","unstructured":"B\u0142a\u017cwicz, J., Liu, Z.: Scheduling multiprocessor tasks with chain constraints. Eur. J. Oper. Res. 94(2), 231\u2013241 (1996). https:\/\/doi.org\/10.1016\/0377-2217(96)00126-9","journal-title":"Eur. J. Oper. Res."},{"key":"11_CR11","doi-asserted-by":"publisher","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"3","key":"11_CR12","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s00453-014-9944-y","volume":"71","author":"M Elberfeld","year":"2015","unstructured":"Elberfeld, M., Stockhusen, C., Tantau, T.: On the space and circuit complexity of parameterized problems: classes and completeness. Algorithmica 71(3), 661\u2013701 (2015). https:\/\/doi.org\/10.1007\/s00453-014-9944-y","journal-title":"Algorithmica"},{"key":"11_CR13","unstructured":"Engels, D.W.: Scheduling for Hardware\/Software Partitioning in Embedded System Design. Ph.D. thesis, Massachusetts Institute of Technology (2000). https:\/\/dspace.mit.edu\/bitstream\/handle\/1721.1\/86443\/46804459-MIT.pdf"},{"issue":"3","key":"11_CR14","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"MR Garey","year":"1978","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S., Knuth, D.E.: Complexity results for bandwidth minimization. SIAM J. Appl. Math. 34(3), 477\u2013495 (1978). https:\/\/doi.org\/10.1137\/0134037","journal-title":"SIAM J. Appl. Math."},{"key":"11_CR15","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 174. Freeman, San Francisco (1979)"},{"key":"11_CR16","doi-asserted-by":"publisher","unstructured":"Graham, R., Lawler, E., Lenstra, J., Kan, A.: Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Hammer, P., Johnson, E., Korte, B. (eds.) Discrete Optimization II, Annals of Discrete Mathematics, vol. 5, pp. 287\u2013326. Elsevier (1979). https:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1016\/0196-6774(84)90006-3","volume":"5","author":"EM Gurari","year":"1984","unstructured":"Gurari, E.M., Sudborough, I.H.: Improved dynamic programming algorithms for bandwidth minimization and the MinCut linear arrangement problem. J. Algorithms 5, 531\u2013546 (1984). https:\/\/doi.org\/10.1016\/0196-6774(84)90006-3","journal-title":"J. Algorithms"},{"key":"11_CR18","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/J.TCS.2018.12.019","volume":"775","author":"F Gurski","year":"2019","unstructured":"Gurski, F., Rehs, C., Rethmann, J.: Knapsack problems: a parameterized point of view. Theor. Comput. Sci. 775, 93\u2013108 (2019). https:\/\/doi.org\/10.1016\/J.TCS.2018.12.019","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"11_CR19","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.jcss.2012.04.004","volume":"79","author":"K Jansen","year":"2013","unstructured":"Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79(1), 39\u201349 (2013). https:\/\/doi.org\/10.1016\/j.jcss.2012.04.004","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"11_CR20","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra, H.W., Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983). https:\/\/doi.org\/10.1287\/moor.8.4.538","journal-title":"Math. Oper. Res."},{"issue":"3","key":"11_CR21","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1137\/0213040","volume":"13","author":"JT Leung","year":"1984","unstructured":"Leung, J.T., Vornberger, O., Witthoff, J.: On some variants of the bandwidth minimization problem. SIAM J. Comput. 13(3), 650\u2013667 (1984). https:\/\/doi.org\/10.1137\/0213040","journal-title":"SIAM J. Comput."},{"key":"11_CR22","unstructured":"Mallem, M.: Parameterized Complexity and New Efficient Enumerative Schemes for RCPSP. Ph.D. thesis, Sorbonne Universit\u00e9 (2024). https:\/\/theses.hal.science\/tel-04910718v1\/file\/146301_MALLEM_2024_archivage.pdf"},{"issue":"3","key":"11_CR23","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10878-026-01411-w","volume":"51","author":"M Mallem","year":"2026","unstructured":"Mallem, M., Hanen, C., Munier-Kordon, A.: Single machine scheduling with precedence constraints and bounded maximum delay value. J. Comb. Optim. 51(3), 33 (2026). https:\/\/doi.org\/10.1007\/s10878-026-01411-w","journal-title":"J. Comb. Optim."},{"issue":"1","key":"11_CR24","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0166-218X(83)90021-5","volume":"5","author":"A Mansfield","year":"1983","unstructured":"Mansfield, A.: On the computational complexity of a merge recognition problem. Discret. Appl. Math. 5(1), 119\u2013122 (1983). https:\/\/doi.org\/10.1016\/0166-218X(83)90021-5","journal-title":"Discret. Appl. Math."},{"key":"11_CR25","doi-asserted-by":"publisher","unstructured":"Pilipczuk, M., Wrochna, M.: On space efficiency of algorithms working on structural decompositions of graphs. ACM Trans. Comput. Theory 9(4), 18:1\u201318:36 (2018). https:\/\/doi.org\/10.1145\/3154856","DOI":"10.1145\/3154856"},{"key":"11_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-38536-0_21","volume-title":"Computer Science \u2013 Theory and Applications","author":"R Rizzi","year":"2013","unstructured":"Rizzi, R., Vialette, S.: On recognizing words that are squares for the shuffle product. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol. 7913, pp. 235\u2013245. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38536-0_21"},{"key":"11_CR27","doi-asserted-by":"publisher","unstructured":"Saxe, J.B.: Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Algebraic Discrete Methods 1(4), 363\u2013369 (1980). https:\/\/doi.org\/10.1137\/0601042","DOI":"10.1137\/0601042"},{"issue":"3","key":"11_CR28","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","volume":"10","author":"J Ullman","year":"1975","unstructured":"Ullman, J.: NP-complete scheduling problems. J. Comput. Syst. Sci. 10(3), 384\u2013393 (1975). https:\/\/doi.org\/10.1016\/S0022-0000(75)80008-0","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"11_CR29","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0022-0000(84)90018-7","volume":"28","author":"MK Warmuth","year":"1984","unstructured":"Warmuth, M.K., Haussler, D.: On the complexity of iterated shuffle. J. Comput. Syst. Sci. 28(3), 345\u2013358 (1984). https:\/\/doi.org\/10.1016\/0022-0000(84)90018-7","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-27732-9_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:37Z","timestamp":1780780477000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-27732-9_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032277312","9783032277329"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-27732-9_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"7 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Clermont-Ferrand","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2026.limos.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}