{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T18:58:23Z","timestamp":1742929103160,"version":"3.40.3"},"publisher-location":"Cham","reference-count":47,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031754081"},{"type":"electronic","value":"9783031754098"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-75409-8_16","type":"book-chapter","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:10:17Z","timestamp":1737497417000},"page":"220-235","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Parameterized Complexity Landscape of\u00a0the\u00a0Unsplittable Flow Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7762-8045","authenticated-orcid":false,"given":"Robert","family":"Ganian","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7158-9022","authenticated-orcid":false,"given":"Mathis","family":"Rocton","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Unterberger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,22]]},"reference":[{"issue":"1\u20132","key":"16_CR1","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s10107-017-1218-4","volume":"172","author":"A Adamaszek","year":"2018","unstructured":"Adamaszek, A., Chalermsook, P., Ene, A., Wiese, A.: Submodular unsplittable flow on trees. Math. Program. 172(1\u20132), 565\u2013589 (2018)","journal-title":"Math. Program."},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Anagnostopoulos, A., Grandoni, F., Leonardi, S., Wiese, A.: A mazing $$2+{\\epsilon }$$ approximation for unsplittable flow on a path. ACM Trans. Algorithms 14(4), 55:1\u201355:23 (2018)","DOI":"10.1145\/3242769"},{"key":"16_CR3","unstructured":"Balab\u00e1n, J., Ganian, R., Rocton, M.: Computing twin-width parameterized by the feedback edge number. In: 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024)"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Batra, J., Garg, N., Kumar, A., M\u00f6mke, T., Wiese, A.: New approximation schemes for unsplittable flow on a path. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 47\u201358. SIAM (2015)","DOI":"10.1137\/1.9781611973730.5"},{"issue":"2","key":"16_CR5","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1287\/moor.25.2.255.12228","volume":"25","author":"A Baveja","year":"2000","unstructured":"Baveja, A., Srinivasan, A.: Approximation algorithms for disjoint paths and related routing and packing problems. Math. Oper. Res. 25(2), 255\u2013280 (2000)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"16_CR6","doi-asserted-by":"publisher","first-page":"603","DOI":"10.7155\/jgaa.00526","volume":"24","author":"S Bhore","year":"2020","unstructured":"Bhore, S., Ganian, R., Montecchiani, F., N\u00f6llenburg, M.: Parameterized algorithms for book embedding problems. J. Graph Algorithms Appl. 24(4), 603\u2013620 (2020)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"16_CR7","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A c$$ ^{\\text{ k }}$$ n 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016)","journal-title":"SIAM J. Comput."},{"key":"16_CR8","unstructured":"Bodlaender, H.L., Groenland, C., Pilipczuk, M.: Parameterized complexity of binary CSP: vertex cover, treedepth, and related parameters. In: 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, LIPIcs, vol. 261, pp. 27:1\u201327:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Bonsma, P.S., Schulz, J., Wiese, A.: A constant factor approximation algorithm for unsplittable flow on paths. In: IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 47\u201356. IEEE Computer Society (2011)","DOI":"10.1109\/FOCS.2011.10"},{"issue":"2","key":"16_CR10","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1137\/120868360","volume":"43","author":"PS Bonsma","year":"2014","unstructured":"Bonsma, P.S., Schulz, J., Wiese, A.: A constant-factor approximation algorithm for unsplittable flow on paths. SIAM J. Comput. 43(2), 767\u2013799 (2014)","journal-title":"SIAM J. Comput."},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"C\u0103linescu, G., Chakrabarti, A., Karloff, H.J., Rabani, Y.: An improved approximation algorithm for resource allocation. ACM Trans. Algorithms 7(4):48:1\u201348:7 (2011)","DOI":"10.1145\/2000807.2000816"},{"key":"16_CR12","unstructured":"Chaplick, S., Di Giacomo, E., Frati, F., Ganian, R., Raftopoulou, C.N., Simonov, K.: Parameterized algorithms for upward planarity. In: 38th International Symposium on Computational Geometry, SoCG 2022. LIPIcs, vol. 224, pp. 26:1\u201326:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/978-3-642-03685-9_4","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"C Chekuri","year":"2009","unstructured":"Chekuri, C., Ene, A., Korula, N.: Unsplittable flow in paths and trees and column-restricted packing integer programs. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX\/RANDOM -2009. LNCS, vol. 5687, pp. 42\u201355. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03685-9_4"},{"issue":"3","key":"16_CR14","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/1273340.1273343","volume":"3","author":"C Chekuri","year":"2007","unstructured":"Chekuri, C., Mydlarz, M., Bruce Shepherd, F.: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms 3(3), 27 (2007)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"16_CR15","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1007\/s00453-011-9502-9","volume":"63","author":"M Chrobak","year":"2012","unstructured":"Chrobak, M., Woeginger, G.J., Makino, K., Haifeng, X.: Caching is hard - even in the fault model. Algorithmica 63(4), 781\u2013794 (2012)","journal-title":"Algorithmica"},{"key":"16_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015)"},{"key":"16_CR17","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Cham (2012)","edition":"4"},{"key":"16_CR18","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer, Cham (2013)"},{"key":"16_CR19","unstructured":"Eiben, E., Ganian, R., Kanj, I.: The parameterized complexity of coordinated motion planning. In: 39th International Symposium on Computational Geometry, SoCG 2023. LIPIcs, vol. 258, pp. 28:1\u201328:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"issue":"1\u20132","key":"16_CR20","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s10107-017-1199-3","volume":"171","author":"K Fleszar","year":"2018","unstructured":"Fleszar, K., Mnich, M., Spoerhase, J.: New algorithms for maximum disjoint paths based on tree-likeness. Math. Program. 171(1\u20132), 433\u2013461 (2018)","journal-title":"Math. Program."},{"key":"16_CR21","unstructured":"Ganian, R., Hamm, T., Korchemna, V., Okrasa, K., Simonov, K.: The complexity of k-means clustering when little is known. In: International Conference on Machine Learning, ICML 2022. Proceedings of Machine Learning Research, vol. 162, pp. 6960\u20136987. PMLR (2022)"},{"issue":"4","key":"16_CR22","doi-asserted-by":"publisher","first-page":"2635","DOI":"10.1137\/20M137478X","volume":"36","author":"R Ganian","year":"2022","unstructured":"Ganian, R., Kim, E.J., Szeider, S.: Algorithmic applications of tree-cut width. SIAM J. Discret. Math. 36(4), 2635\u20132666 (2022)","journal-title":"SIAM J. Discret. Math."},{"key":"16_CR23","unstructured":"Ganian, R., Korchemna, V.: Slim tree-cut width. In: 17th International Symposium on Parameterized and Exact Computation, IPEC 2022. LIPIcs, vol. 249, pp. 15:1\u201315:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"issue":"2","key":"16_CR24","doi-asserted-by":"publisher","first-page":"726","DOI":"10.1007\/s00453-020-00772-w","volume":"83","author":"R Ganian","year":"2021","unstructured":"Ganian, R., Ordyniak, S.: The power of cut-based parameters for computing edge-disjoint paths. Algorithmica 83(2), 726\u2013752 (2021)","journal-title":"Algorithmica"},{"issue":"6","key":"16_CR25","doi-asserted-by":"publisher","first-page":"1605","DOI":"10.1007\/s00453-020-00795-3","volume":"83","author":"R Ganian","year":"2021","unstructured":"Ganian, R., Ordyniak, S., Ramanujan, M.S.: On structural parameterizations of the edge disjoint paths problem. Algorithmica 83(6), 1605\u20131637 (2021)","journal-title":"Algorithmica"},{"issue":"1","key":"16_CR26","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3\u201320 (1997)","journal-title":"Algorithmica"},{"key":"16_CR27","unstructured":"Grandoni, F., M\u00f6mke, T., Wiese, A.: Faster (1+$$\\epsilon $$)-approximation for unsplittable flow on a path via resource augmentation and back. In: 29th Annual European Symposium on Algorithms, ESA 2021. LIPIcs, vol. 204, pp. 49:1\u201349:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"16_CR28","doi-asserted-by":"crossref","unstructured":"Grandoni, F., M\u00f6mke, T., Wiese, A.: A PTAS for unsplittable flow on a path. In: STOC 2022: 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 289\u2013302. ACM (2022)","DOI":"10.1145\/3519935.3519959"},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"Grandoni, F., M\u00f6mke, T., Wiese, A.: Unsplittable flow on a path: the game! In: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 906\u2013926. SIAM (2022)","DOI":"10.1137\/1.9781611977073.39"},{"key":"16_CR30","doi-asserted-by":"crossref","unstructured":"Grandoni, F., M\u00f6mke, T., Wiese, A., Zhou, H.: To augment or not to augment: solving unsplittable flow on a path by creating slack. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2411\u20132422. SIAM (2017)","DOI":"10.1137\/1.9781611974782.159"},{"issue":"3","key":"16_CR31","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/S0022-0000(03)00066-7","volume":"67","author":"V Guruswami","year":"2003","unstructured":"Guruswami, V., Khanna, S., Rajaraman, R., Bruce Shepherd, F., Yannakakis, M.: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67(3), 473\u2013496 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-642-13731-0_25","volume-title":"Algorithm Theory - SWAT 2010","author":"K Jansen","year":"2010","unstructured":"Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol. 6139, pp. 260\u2013272. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13731-0_25"},{"key":"16_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. Lecture Notes in Computer Science, vol. 842. Computations and Approximations, Springer, Cham (1994)"},{"key":"16_CR34","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.jcss.2022.10.001","volume":"132","author":"T Koana","year":"2023","unstructured":"Koana, T., Froese, V., Niedermeier, R.: The complexity of binary matrix completion under diameter constraints. J. Comput. Syst. Sci. 132, 45\u201367 (2023)","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR35","doi-asserted-by":"publisher","unstructured":"Kolman, P., Scheideler, C.: Simple on-line algorithms for the maximum disjoint paths problem. In: Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2001, pp. 38\u201347. Association for Computing Machinery, New York (2001). https:\/\/doi.org\/10.1145\/378580.378586","DOI":"10.1145\/378580.378586"},{"issue":"1","key":"16_CR36","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.jalgor.2004.07.006","volume":"61","author":"P Kolman","year":"2006","unstructured":"Kolman, P., Scheideler, C.: Improved bounds for the unsplittable flow problem. J. Algorithms 61(1), 20\u201344 (2006)","journal-title":"J. Algorithms"},{"key":"16_CR37","unstructured":"Korhonen, J.H., Parviainen, P.: Tractable Bayesian network structure learning with bounded vertex cover number. In: Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, pp. 622\u2013630 (2015)"},{"key":"16_CR38","doi-asserted-by":"crossref","unstructured":"Korhonen, T.: A single-exponential time 2-approximation algorithm for treewidth. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pp. 184\u2013192. IEEE (2021)","DOI":"10.1109\/FOCS52979.2021.00026"},{"key":"16_CR39","doi-asserted-by":"crossref","unstructured":"Martens, M., Skutella, M.: Length-bounded and dynamic k-splittable flows. In: Operations Research Proceedings 2005, Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), pp. 297\u2013302 (2005)","DOI":"10.1007\/3-540-32539-5_47"},{"key":"16_CR40","unstructured":"Mart\u00ednez-Mu\u00f1oz, T., Wiese, A.: FPT and FPT-approximation algorithms for unsplittable flow on trees. In: 29th Annual European Symposium on Algorithms, ESA 2021. LIPIcs, vol. 204, pp. 67:1\u201367:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"issue":"1\u20133","key":"16_CR41","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/j.dam.2003.12.003","volume":"143","author":"D Marx","year":"2004","unstructured":"Marx, D.: Eulerian disjoint paths problem in grid graphs is NP-complete. Discret. Appl. Math. 143(1\u20133), 336\u2013341 (2004)","journal-title":"Discret. Appl. Math."},{"key":"16_CR42","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity - Graphs, Structures, and Algorithms","author":"J Nesetril","year":"2012","unstructured":"Nesetril, J., de Mendez, P.O.: Sparsity - Graphs, Structures, and Algorithms. Algorithms and Combinatorics, vol. 28. Springer, Cham (2012)"},{"key":"16_CR43","unstructured":"Phillips, C.A., Uma, R.N., Wein, J.: Off-line admission control for general scheduling problems. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 879\u2013888. ACM\/SIAM (2000)"},{"issue":"3","key":"16_CR44","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"16_CR45","unstructured":"Wiese, A.: A (1+epsilon)-approximation for unsplittable flow on a path in fixed-parameter running time. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. LIPIcs, vol.\u00a080, pp. 67:1\u201367:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"key":"16_CR46","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.jctb.2014.07.003","volume":"110","author":"P Wollan","year":"2015","unstructured":"Wollan, P.: The structure of graphs not admitting a fixed immersion. J. Comb. Theory Ser. B 110, 47\u201366 (2015)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"16_CR47","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1137\/130924056","volume":"28","author":"P Wollan","year":"2014","unstructured":"Wollan, P., Marx, D.: Immersions in highly edge connected graphs. SIAM J. Discret. Math. 28(1), 503\u2013520 (2014)","journal-title":"SIAM J. Discret. Math."}],"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-031-75409-8_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:10:35Z","timestamp":1737497435000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-75409-8_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031754081","9783031754098"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-75409-8_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"22 January 2025","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":"Gozd Martuljek","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovenia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conferences.famnit.upr.si\/event\/31\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}