{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:46:38Z","timestamp":1787496398009,"version":"build-2736575974"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2018,1,22]],"date-time":"2018-01-22T00:00:00Z","timestamp":1516579200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100007543","name":"Grantov\u00e1 Agentura, Univerzita Karlova","doi-asserted-by":"publisher","award":["1784214"],"award-info":[{"award-number":["1784214"]}],"id":[{"id":"10.13039\/100007543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u00c7esk\u00e9 Republiky","doi-asserted-by":"publisher","award":["CE-ITI P202\/12\/G061"],"award-info":[{"award-number":["CE-ITI P202\/12\/G061"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007543","name":"Grantov\u00e1 Agentura, Univerzita Karlova","doi-asserted-by":"publisher","award":["SVV-2016- 260332"],"award-info":[{"award-number":["SVV-2016- 260332"]}],"id":[{"id":"10.13039\/100007543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001823","name":"Ministerstvo \u0160kolstv\u00ed, Ml\u00e1de\u017ee a T\u011blov\u00fdchovy","doi-asserted-by":"publisher","award":["Kontakt LH12095"],"award-info":[{"award-number":["Kontakt LH12095"]}],"id":[{"id":"10.13039\/501100001823","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["616787"],"award-info":[{"award-number":["616787"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s00453-018-0408-7","type":"journal-article","created":{"date-parts":[[2018,1,22]],"date-time":"2018-01-22T10:38:06Z","timestamp":1516617486000},"page":"3597-3617","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Parameterized Complexity of Length-bounded Cuts and Multicuts"],"prefix":"10.1007","volume":"80","author":[{"given":"Pavel","family":"Dvo\u0159\u00e1k","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2588-5709","authenticated-orcid":false,"given":"Du\u0161an","family":"Knop","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,1,22]]},"reference":[{"issue":"4","key":"408_CR1","first-page":"661","volume":"12","author":"J Ad\u00e1mek","year":"1971","unstructured":"Ad\u00e1mek, J., Koubek, V.: Remarks on flows in network with short paths. Comment. Math. Univ. Carol. 12(4), 661\u2013667 (1971)","journal-title":"Comment. Math. Univ. Carol."},{"issue":"1","key":"408_CR2","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/1868237.1868241","volume":"7","author":"G Baier","year":"2010","unstructured":"Baier, G., Erlebach, T., Hall, A., K\u00f6hler, E., Kolman, P., Pangr\u00e1c, O., Schilling, H., Skutella, M.: Length-bounded cuts and flows. ACM Trans. Algorithms 7(1), 4:1\u20134:27 (2010). https:\/\/doi.org\/10.1145\/1868237.1868241","journal-title":"ACM Trans. Algorithms"},{"key":"408_CR3","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009). https:\/\/doi.org\/10.1016\/j.jcss.2009.04.001, http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000009000282","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"408_CR4","unstructured":"Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: Handbook of Theoretical Computer Science, pp. 194\u2013242 (1990). http:\/\/ci.nii.ac.jp\/naid\/10009893142\/en\/"},{"key":"408_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"408_CR6","doi-asserted-by":"publisher","unstructured":"Dahl, G., Gouveia, L.: On the directed hop-constrained shortest path problem. Oper. Res. Lett. 32(1), 15\u201322 (2004). https:\/\/doi.org\/10.1016\/S0167-6377(03)00026-9, http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0167637703000269","DOI":"10.1016\/S0167-6377(03)00026-9"},{"key":"408_CR7","series-title":"Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-79723-4_9","volume-title":"Parameterized and Exact Computation","author":"M Dom","year":"2008","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: Grohe, M., Niedermeier, R. (eds.) Parameterized and Exact Computation. Lecture notes in computer science, vol. 5018, pp. 78\u201390. Springer, Berlin (2008). https:\/\/doi.org\/10.1007\/978-3-540-79723-4_9"},{"key":"408_CR8","doi-asserted-by":"publisher","unstructured":"Dvo\u0159\u00e1k, P., Knop, D.: Parametrized complexity of length-bounded cuts and multi-cuts. In: Proceedings of Theory and Applications of Models of Computation\u201412th Annual Conference, TAMC 2015, Singapore, May 18\u201320, 2015, pp. 441\u2013452 (2015). https:\/\/doi.org\/10.1007\/978-3-319-17142-5_37","DOI":"10.1007\/978-3-319-17142-5_37"},{"issue":"6","key":"408_CR9","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"RW Floyd","year":"1962","unstructured":"Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962). https:\/\/doi.org\/10.1145\/367766.368168","journal-title":"Commun. ACM"},{"key":"408_CR10","doi-asserted-by":"publisher","unstructured":"Fluschnik, T., Hermelin, D., Nichterlein, A., Niedermeier, R.: Fractals for kernelization lower bounds, with an application to length-bounded cut problems. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11\u201315, 2016, Rome, Italy, pp. 25:1\u201325:14 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.25","DOI":"10.4230\/LIPIcs.ICALP.2016.25"},{"issue":"3","key":"408_CR11","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8(3), 399\u2013404 (1956)","journal-title":"Can. J. Math."},{"key":"408_CR12","unstructured":"Freuder, E.C.: Complexity of k-tree structured constraint satisfaction problems. In: Shrobe, H.E., Dietterich, T.G., Swartout, W.R. (eds.) Proceedings of the 8th National Conference on Artificial Intelligence, Boston, Massachusetts, July 29\u2013August 3, 1990, vol. 2, pp. 4\u20139. AAAI Press\/The MIT Press (1990). http:\/\/www.aaai.org\/Library\/AAAI\/1990\/aaai90-001.php"},{"key":"408_CR13","unstructured":"Ganian, R., Ordyniak, S.: The complexity landscape of decompositional parameters for ILP. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12\u201317, 2016, Phoenix, Arizona, USA, pp. 710\u2013716 (2016). http:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI16\/paper\/view\/12432"},{"key":"408_CR14","doi-asserted-by":"publisher","unstructured":"Golovach, P.A., Thilikos, D.M.: Paths of bounded length and their cuts: parameterized complexity and algorithms. Discret. Optim. 8(1), 72\u201386 (2011). https:\/\/doi.org\/10.1016\/j.disopt.2010.09.009, http:\/\/www.sciencedirect.com\/science\/article\/pii\/S1572528610000678","DOI":"10.1016\/j.disopt.2010.09.009"},{"key":"408_CR15","doi-asserted-by":"publisher","unstructured":"Gutin, G., Jones, M., Wahlstr\u00f6m, M.: Structural parameterizations of the mixed Chinese postman problem. In: Bansal, N., Finocchi, I. (eds.) Algorithms ESA 2015, Lecture Notes in Computer Science, vol. 9294, pp. 668\u2013679. Springer Berlin (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_56","DOI":"10.1007\/978-3-662-48350-3_56"},{"issue":"1","key":"408_CR16","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1002\/net.20146","volume":"49","author":"D Huygens","year":"2007","unstructured":"Huygens, D., Labb\u00e9, M., Mahjoub, A.R., Pesneau, P.: The two-edge connected hop-constrained network design problem: valid inequalities and branch-and-cut. Networks 49(1), 116\u2013133 (2007). https:\/\/doi.org\/10.1002\/net.20146","journal-title":"Networks"},{"issue":"3","key":"408_CR17","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1002\/net.3230120306","volume":"12","author":"A Itai","year":"1982","unstructured":"Itai, A., Perl, Y., Shiloach, Y.: The complexity of finding maximum disjoint paths with length constraints. Networks 12(3), 277\u2013286 (1982). https:\/\/doi.org\/10.1002\/net.3230120306","journal-title":"Networks"},{"key":"408_CR18","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth, Computations and Approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. Lecture notes in computer science, vol. 842. Springer, New York, Inc (1994)"},{"key":"408_CR19","unstructured":"Kolman, P.: On algorithms for $$l$$l-bounded cut problem. CoRR abs\/1705.02390 (2017). arXiv:1705.02390"},{"key":"408_CR20","doi-asserted-by":"publisher","unstructured":"Ne\u0161et\u0159il, J., de\u00a0Mendez, P.O.: Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb. 27(6), 1022\u20131041 (2006). https:\/\/doi.org\/10.1016\/j.ejc.2005.01.010, http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0195669805000570","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"408_CR21","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., de\u00a0Mendez, P.: Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics. Springer, Berlin (2012). https:\/\/books.google.cz\/books?id=n8UuUePJ_iIC","DOI":"10.1007\/978-3-642-27875-4"},{"key":"408_CR22","doi-asserted-by":"publisher","unstructured":"Orlin, J.B.: Max flows in o(nm) time, or better. In: Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, CA, USA, June 1\u20134, 2013, pp. 765\u2013774 (2013). https:\/\/doi.org\/10.1145\/2488608.2488705","DOI":"10.1145\/2488608.2488705"},{"issue":"1","key":"408_CR23","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S Warshall","year":"1962","unstructured":"Warshall, S.: A theorem on Boolean matrices. J. ACM 9(1), 11\u201312 (1962). https:\/\/doi.org\/10.1145\/321105.321107","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0408-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0408-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0408-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,9]],"date-time":"2019-10-09T13:21:02Z","timestamp":1570627262000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0408-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,22]]},"references-count":23,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["408"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0408-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,22]]}}}