{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:40:56Z","timestamp":1767314456276,"version":"3.48.0"},"publisher-location":"Cham","reference-count":54,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032118349","type":"print"},{"value":"9783032118356","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-11835-6_8","type":"book-chapter","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:39:02Z","timestamp":1767314342000},"page":"105-120","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Concurrency Constrained Scheduling with\u00a0Tree-Like Constraints"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9297-3330","authenticated-orcid":false,"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6379-0383","authenticated-orcid":false,"given":"Danny","family":"Hermelin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5240-7257","authenticated-orcid":false,"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,2]]},"reference":[{"key":"8_CR1","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF01956769","volume":"42","author":"N Alon","year":"1983","unstructured":"Alon, N.: A note on the decomposition of graphs into isomorphic matchings. Acta Math. Hungar. 42, 221\u2013223 (1983). https:\/\/doi.org\/10.1007\/BF01956769","journal-title":"Acta Math. Hungar."},{"issue":"2","key":"8_CR2","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(96)00031-X","volume":"162","author":"BS Baker","year":"1996","unstructured":"Baker, B.S., Coffman, E.G., Jr.: Mutual exclusion scheduling. Theor. Comput. Sci. 162(2), 225\u2013243 (1996). https:\/\/doi.org\/10.1016\/0304-3975(96)00031-X","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"8_CR3","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1137\/0220012","volume":"20","author":"E Balas","year":"1991","unstructured":"Balas, E., Xue, J.: Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs. SIAM J. Comput. 20(2), 209\u2013221 (1991). https:\/\/doi.org\/10.1137\/0220012","journal-title":"SIAM J. Comput."},{"issue":"5","key":"8_CR4","doi-asserted-by":"publisher","first-page":"1000","DOI":"10.1137\/0221058","volume":"21","author":"E Balas","year":"1992","unstructured":"Balas, E., Xue, J.: Addendum: Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs. SIAM J. Comput. 21(5), 1000 (1992). https:\/\/doi.org\/10.1137\/0221058","journal-title":"SIAM J. Comput."},{"issue":"2","key":"8_CR5","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1006\/INCO.1997.2677","volume":"140","author":"A Bar-Noy","year":"1998","unstructured":"Bar-Noy, A., Bellare, M., Halld\u00f3rsson, M.M., Shachnai, H., Tamir, T.: On chromatic sums and distributed resource allocation. Inf. Comput. 140(2), 183\u2013202 (1998). https:\/\/doi.org\/10.1006\/INCO.1997.2677","journal-title":"Inf. Comput."},{"issue":"2","key":"8_CR6","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1006\/JAGM.2000.1106","volume":"37","author":"A Bar-Noy","year":"2000","unstructured":"Bar-Noy, A., Halld\u00f3rsson, M.M., Kortsarz, G., Salman, R., Shachnai, H.: Sum multicoloring of graphs. J. Algor. 37(2), 422\u2013450 (2000). https:\/\/doi.org\/10.1006\/JAGM.2000.1106","journal-title":"J. Algor."},{"issue":"2","key":"8_CR7","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1006\/JAGM.1998.0938","volume":"28","author":"A Bar-Noy","year":"1998","unstructured":"Bar-Noy, A., Kortsarz, G.: Minimum color sum of bipartite graphs. J. Algor. 28(2), 339\u2013365 (1998). https:\/\/doi.org\/10.1006\/JAGM.1998.0938","journal-title":"J. Algor."},{"issue":"3","key":"8_CR8","doi-asserted-by":"publisher","first-page":"1761","DOI":"10.1137\/20M1385779","volume":"36","author":"R Belmonte","year":"2022","unstructured":"Belmonte, R., Kim, E.J., Lampis, M., Mitsou, V., Otachi, Y.: Grundy distinguishes treewidth from pathwidth. SIAM J. Disc. Math. 36(3), 1761\u20131787 (2022). https:\/\/doi.org\/10.1137\/20M1385779","journal-title":"SIAM J. Disc. Math."},{"issue":"1","key":"8_CR9","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/J.TCS.2005.09.027","volume":"349","author":"HL Bodlaender","year":"2005","unstructured":"Bodlaender, H.L., Fomin, F.V.: Equitable colorings of bounded treewidth graphs. Theor. Comput. Sci. 349(1), 22\u201330 (2005). https:\/\/doi.org\/10.1016\/J.TCS.2005.09.027","journal-title":"Theor. Comput. Sci."},{"key":"8_CR10","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L.,\u00a0Groenland, C.,\u00a0Jacob, H.,\u00a0Pilipczuk, M.,\u00a0Pilipczuk, M.: On the complexity of problems on tree-structured graphs. In:\u00a0Dell, H.,\u00a0Nederlof, J. (eds.) 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, vol. 249 of LIPIcs, 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":"8_CR11","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.: 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":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/3-540-57182-5_21","volume-title":"Mathematical Foundations of Computer Science 1993","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L., Jansen, K.: On the complexity of scheduling incompatible jobs with unit-times. In: Borzyszkowski, A.M., Soko\u0142owski, S. (eds.) MFCS 1993. LNCS, vol. 711, pp. 291\u2013300. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-57182-5_21"},{"issue":"1","key":"8_CR13","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0304-3975(95)00057-4","volume":"148","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Jansen, K.: Restrictions of graph partition problems. Part I. Theor. Comput. Sci. 148(1), 93\u2013109 (1995). https:\/\/doi.org\/10.1016\/0304-3975(95)00057-4","journal-title":"Theor. Comput. Sci."},{"key":"8_CR14","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L.,\u00a0Mannens, I., Oostveen, J.J.,\u00a0Pandey, S., van Leeuwen, E.J.: The parameterised complexity of integer multicommodity flow. In:\u00a0Misra, N.,\u00a0Wahlstr\u00f6m, M. (eds.) Proceedings of the 18th International Symposium on Parameterized and Exact Computation, IPEC 2023, vol. 285 of LIPIcs, pp. 6:1\u20136:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPICS.IPEC.2023.6","DOI":"10.4230\/LIPICS.IPEC.2023.6"},{"key":"8_CR15","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L.,\u00a0Szil\u00e1gyi, K.: XNLP-hardness of parameterized problems on planar graphs. In:\u00a0Kr\u00e1l, D.,\u00a0Milanic, M. (eds.) Proceedings of the 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024, vol. 14760 of Lecture Notes in Computer Science, pp. 107\u2013120. Springer, Heidelberg (2024). https:\/\/doi.org\/10.1007\/978-3-031-75409-8_8","DOI":"10.1007\/978-3-031-75409-8_8"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/J.ENDM.2009.11.048","volume":"35","author":"F Bonomo","year":"2009","unstructured":"Bonomo, F., Valencia-Pabon, M.: Minimum sum coloring of p$$ _{\\text{4 }}$$-sparse graphs. Electron. Notes Disc. Math. 35, 293\u2013298 (2009). https:\/\/doi.org\/10.1016\/J.ENDM.2009.11.048","journal-title":"Electron. Notes Disc. Math."},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/J.TCS.2011.11.010","volume":"418","author":"A Borodin","year":"2012","unstructured":"Borodin, A., Ivan, I., Ye, Y., Zimny, B.: On sum coloring and sum multi-coloring for restricted families of graphs. Theor. Comput. Sci. 418, 1\u201313 (2012). https:\/\/doi.org\/10.1016\/J.TCS.2011.11.010","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"8_CR18","doi-asserted-by":"publisher","first-page":"744","DOI":"10.1137\/0214054","volume":"14","author":"EG Coffman Jr","year":"1985","unstructured":"Coffman, E.G., Jr., Garey, M.R., Johnson, D.S., LaPaugh, A.S.: Scheduling file transfers. SIAM J. Comput. 14(3), 744\u2013780 (1985). https:\/\/doi.org\/10.1137\/0214054","journal-title":"SIAM J. Comput."},{"key":"8_CR19","doi-asserted-by":"publisher","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th edn, vol. 173 of Graduate Texts in Mathematics. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-662-53622-3_7"},{"issue":"3","key":"8_CR21","doi-asserted-by":"publisher","first-page":"1068","DOI":"10.1137\/110855806","volume":"26","author":"V Dujmovic","year":"2012","unstructured":"Dujmovic, V., Joret, G., Wood, D.R.: An improved bound for first-fit on posets without two long incomparable chains. SIAM J. Disc. Math. 26(3), 1068\u20131075 (2012). https:\/\/doi.org\/10.1137\/110855806","journal-title":"SIAM J. Disc. Math."},{"issue":"3","key":"8_CR22","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s00453-014-9944-y","volume":"71","author":"M Elberfeld","year":"2014","unstructured":"Elberfeld, M., Stockhusen, C., Tantau, T.: On the space and circuit complexity of parameterized problems: classes and completeness. Algorithmica 71(3), 661\u2013701 (2014). https:\/\/doi.org\/10.1007\/s00453-014-9944-y","journal-title":"Algorithmica"},{"issue":"2","key":"8_CR23","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/J.IC.2010.11.026","volume":"209","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., et al.: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209(2), 143\u2013153 (2011). https:\/\/doi.org\/10.1016\/J.IC.2010.11.026","journal-title":"Inf. Comput."},{"key":"8_CR24","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"issue":"2","key":"8_CR25","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1(2), 180\u2013187 (1972). https:\/\/doi.org\/10.1137\/0201013","journal-title":"SIAM J. Comput."},{"key":"8_CR26","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"8_CR27","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"3","author":"R Graham","year":"1979","unstructured":"Graham, R., Lawler, E., Lenstra, J., Kan, A.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Disc. Math. 3, 287\u2013326 (1979). https:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X","journal-title":"Ann. Disc. Math."},{"key":"8_CR28","doi-asserted-by":"publisher","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/978-3-642-97881-4","DOI":"10.1007\/978-3-642-97881-4"},{"issue":"2","key":"8_CR29","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1006\/JAGM.2001.1210","volume":"42","author":"MM Halld\u00f3rsson","year":"2002","unstructured":"Halld\u00f3rsson, M.M., Kortsarz, G.: Tools for multicoloring with applications to planar graphs and partial $$k$$-trees. J. Algor. 42(2), 334\u2013366 (2002). https:\/\/doi.org\/10.1006\/JAGM.2001.1210","journal-title":"J. Algor."},{"issue":"1\u20133","key":"8_CR30","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0012-365X(93)90165-P","volume":"111","author":"P Hansen","year":"1993","unstructured":"Hansen, P., Hertz, A., Kuplinsky, J.: Bounded vertex colorings of graphs. Disc. Math. 111(1\u20133), 305\u2013312 (1993). https:\/\/doi.org\/10.1016\/0012-365X(93)90165-P","journal-title":"Disc. Math."},{"issue":"2","key":"8_CR31","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0166-218X(94)90004-3","volume":"55","author":"CT Ho\u00e0ng","year":"1994","unstructured":"Ho\u00e0ng, C.T.: Efficient algorithms for minimum weighted colouring of some classes of perfect graphs. Disc. Appl. Math. 55(2), 133\u2013143 (1994). https:\/\/doi.org\/10.1016\/0166-218X(94)90004-3","journal-title":"Disc. Appl. Math."},{"key":"8_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/3-540-45655-4_46","volume-title":"Computing and Combinatorics","author":"T Ito","year":"2002","unstructured":"Ito, T., Nishizeki, T., Zhou, X.: Algorithms for the multicolorings of partial k-trees. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2387, pp. 430\u2013439. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45655-4_46"},{"key":"8_CR33","unstructured":"Ito, T.,\u00a0Nishizeki, T.,\u00a0Zhou, X.: Algorithms for multicolorings of partial $$k$$-trees. IEICE Trans. Inf. Syst. E86-D(2), 191\u2013200 (2003). https:\/\/search.ieice.org\/bin\/summary.php?id=e86-d_2_191"},{"key":"8_CR34","doi-asserted-by":"crossref","unstructured":"Jansen, K.: Complexity results for the optimum cost chromatic partition problem. Manuscript (1997)","DOI":"10.1007\/3-540-62592-5_58"},{"key":"8_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/3-540-62592-5_58","volume-title":"Algorithms and Complexity","author":"K Jansen","year":"1997","unstructured":"Jansen, K.: The optimum cost chromatic partition problem. In: Bongiovanni, G., Bovet, D.P., Di Battista, G. (eds.) CIAC 1997. LNCS, vol. 1203, pp. 25\u201336. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-62592-5_58"},{"key":"8_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/3-540-59042-0_92","volume-title":"STACS 95","author":"D Kaller","year":"1995","unstructured":"Kaller, D., Gupta, A., Shermer, T.: The $$\\chi $$t-coloring problem. In: Mayr, E.W., Puech, C. (eds.) STACS 1995. LNCS, vol. 900, pp. 409\u2013420. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-59042-0_92"},{"key":"8_CR37","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a symposium on the Complexity of Computer Computations, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, 20\u201322 March 1972, pp. 85\u2013103. Plenum Press, New York (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"8_CR38","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0012-365X(89)90204-5","volume":"74","author":"M Kubale","year":"1989","unstructured":"Kubale, M.: Interval vertex-coloring of a graph with forbidden colors. Disc. Math. 74(1), 125\u2013136 (1989). https:\/\/doi.org\/10.1016\/0012-365X(89)90204-5","journal-title":"Disc. Math."},{"issue":"30","key":"8_CR39","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1155\/S0161171204306216","volume":"2004","author":"EM Kubicka","year":"2004","unstructured":"Kubicka, E.M.: The chromatic sum of a graph: history and recent developments. Int. J. Math. Math. Sci. 2004(30), 1563\u20131573 (2004). https:\/\/doi.org\/10.1155\/S0161171204306216","journal-title":"Int. J. Math. Math. Sci."},{"key":"8_CR40","doi-asserted-by":"publisher","unstructured":"Kubicka, E.M., Schwenk, A.J.: An introduction to chromatic sums. In: Riehl, A.M. (ed.) Computer Trends in the 1990s - Proceedings of the 1989 ACM 17th Annual Computer Science Conference, Louisville, Kentucky, USA, 21\u201323 February 1989, pp. 39\u201345. ACM (1989). https:\/\/doi.org\/10.1145\/75427.75430","DOI":"10.1145\/75427.75430"},{"key":"8_CR41","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algor. 14(2), 13:1\u201313:30 (2018). https:\/\/doi.org\/10.1145\/3170442","DOI":"10.1145\/3170442"},{"key":"8_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/3-540-55121-2_9","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Z Lonc","year":"1992","unstructured":"Lonc, Z.: On complexity of some chain and antichain partition problems. In: Schmidt, G., Berghammer, R. (eds.) WG 1991. LNCS, vol. 570, pp. 97\u2013104. Springer, Heidelberg (1992). https:\/\/doi.org\/10.1007\/3-540-55121-2_9"},{"issue":"4","key":"8_CR43","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/S00453-004-1111-4","volume":"40","author":"M Malafiejski","year":"2004","unstructured":"Malafiejski, M., Giaro, K., Janczewski, R., Kubale, M.: Sum coloring of bipartite graphs with bounded degree. Algorithmica 40(4), 235\u2013244 (2004). https:\/\/doi.org\/10.1007\/S00453-004-1111-4","journal-title":"Algorithmica"},{"issue":"4","key":"8_CR44","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/J.ORL.2004.07.006","volume":"33","author":"D Marx","year":"2005","unstructured":"Marx, D.: A short proof of the NP-completeness of minimum sum interval coloring. Oper. Res. Lett. 33(4), 382\u2013384 (2005). https:\/\/doi.org\/10.1016\/J.ORL.2004.07.006","journal-title":"Oper. Res. Lett."},{"key":"8_CR45","doi-asserted-by":"crossref","unstructured":"McDiarmid, C., Reed, B.A.: Channel assignment and weighted coloring. Networks 36(2), 114\u2013117 (2000). 10.1002\/1097-0037(200009)36:2$$<$$114::AID-NET6$$>$$3.0.CO;2-G","DOI":"10.1002\/1097-0037(200009)36:2<114::AID-NET6>3.0.CO;2-G"},{"issue":"2","key":"8_CR46","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/PL00009252","volume":"23","author":"S Nicoloso","year":"1999","unstructured":"Nicoloso, S., Sarrafzadeh, M., Song, X.: On the sum coloring problem on interval graphs. Algorithmica 23(2), 109\u2013126 (1999). https:\/\/doi.org\/10.1007\/PL00009252","journal-title":"Algorithmica"},{"key":"8_CR47","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":"8_CR48","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26580-3","volume-title":"Scheduling: Theory, Algorithms, and Systems","author":"M Pinedo","year":"2016","unstructured":"Pinedo, M.: Scheduling: Theory, Algorithms, and Systems, 5th edn. Springer, Heidelberg (2016)","edition":"5"},{"key":"8_CR49","unstructured":"Salavatipour, M.: On sum coloring of graphs. Master\u2019s thesis, University of Toronto (2000). https:\/\/hdl.handle.net\/1807\/15002"},{"issue":"3","key":"8_CR50","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1016\/S0166-218X(02)00249-4","volume":"127","author":"MR Salavatipour","year":"2003","unstructured":"Salavatipour, M.R.: On sum coloring of graphs. Disc. Appl. Math. 127(3), 477\u2013488 (2003). https:\/\/doi.org\/10.1016\/S0166-218X(02)00249-4","journal-title":"Disc. Appl. Math."},{"issue":"1","key":"8_CR51","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1109\/TCAD.1987.1270250","volume":"6","author":"K Supowit","year":"1987","unstructured":"Supowit, K.: Finding a maximum planar subset of a set of nets in a channel. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 6(1), 93\u201394 (1987). https:\/\/doi.org\/10.1109\/TCAD.1987.1270250","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"issue":"1","key":"8_CR52","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1137\/S0097539796303123","volume":"29","author":"T Szkaliczki","year":"1999","unstructured":"Szkaliczki, T.: Routing with minimum wire length in the dogleg-free manhattan model is NP-complete. SIAM J. Comput. 29(1), 274\u2013287 (1999). https:\/\/doi.org\/10.1137\/S0097539796303123","journal-title":"SIAM J. Comput."},{"issue":"4","key":"8_CR53","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"JA Telle","year":"1997","unstructured":"Telle, J.A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial $$k$$-trees. SIAM J. Disc. Math. 10(4), 529\u2013550 (1997). https:\/\/doi.org\/10.1137\/S0895480194275825","journal-title":"SIAM J. Disc. Math."},{"issue":"2","key":"8_CR54","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/S00453-003-1060-3","volume":"38","author":"X Zhou","year":"2004","unstructured":"Zhou, X., Nishizeki, T.: Multicolorings of series-parallel graphs. Algorithmica 38(2), 271\u2013297 (2004). https:\/\/doi.org\/10.1007\/S00453-003-1060-3","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-11835-6_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:39:03Z","timestamp":1767314343000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-11835-6_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032118349","9783032118356"],"references-count":54,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-11835-6_8","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":"2 January 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Otzenhausen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo.uni-trier.de\/wg2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}