{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:45:12Z","timestamp":1767339912712,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2019,8,3]],"date-time":"2019-08-03T00:00:00Z","timestamp":1564790400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,8,3]],"date-time":"2019-08-03T00:00:00Z","timestamp":1564790400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["Veni grant 639.021.437 \u201cFrontiers in Parameterized Preprocessing\u201d","Gravitation grant 024.002.003 \u201cNetworks\u201d"],"award-info":[{"award-number":["Veni grant 639.021.437 \u201cFrontiers in Parameterized Preprocessing\u201d","Gravitation grant 024.002.003 \u201cNetworks\u201d"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001870","name":"Fundacja na rzecz Nauki Polskiej","doi-asserted-by":"publisher","award":["HOMING \u201cRecent trends in kernelization: theory and experimental evaluation\u201d"],"award-info":[{"award-number":["HOMING \u201cRecent trends in kernelization: theory and experimental evaluation\u201d"]}],"id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2013\/11\/D\/ST6\/03073"],"award-info":[{"award-number":["2013\/11\/D\/ST6\/03073"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001870","name":"Fundacja na rzecz Nauki Polskiej","doi-asserted-by":"publisher","award":["START"],"award-info":[{"award-number":["START"]}],"id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s00453-019-00614-4","type":"journal-article","created":{"date-parts":[[2019,8,3]],"date-time":"2019-08-03T06:13:55Z","timestamp":1564812835000},"page":"3936-3967","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor"],"prefix":"10.1007","volume":"81","author":[{"given":"Bart M. P.","family":"Jansen","sequence":"first","affiliation":[]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9346-2172","authenticated-orcid":false,"given":"Marcin","family":"Wrochna","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,8,3]]},"reference":[{"key":"614_CR1","doi-asserted-by":"crossref","unstructured":"Ambalath, A.M., Balasundaram, R.,Rao, R., Koppula, V., Misra, N., Philip, G., Ramanujan, M.S.: On the kernelization complexity of colorful motifs. In: Proceedings of the 5th IPEC, pp. 14\u201325 (2010). \n                    https:\/\/doi.org\/10.1007\/978-3-642-17493-3_4","DOI":"10.1007\/978-3-642-17493-3_4"},{"issue":"5\u201354","key":"614_CR2","first-page":"18","volume":"115","author":"D Archdeacon","year":"1996","unstructured":"Archdeacon, D.: Topological graph theory: a survey. Congr. Numerantium 115(5\u201354), 18 (1996)","journal-title":"Congr. Numerantium"},{"issue":"3","key":"614_CR3","doi-asserted-by":"publisher","first-page":"38:1","DOI":"10.1145\/3196276","volume":"14","author":"F Barbero","year":"2018","unstructured":"Barbero, F., Paul, C., Pilipczuk, M.: Exploring the complexity of layout parameters in tournaments and semicomplete digraphs. ACM Trans. Algorithms 14(3), 38:1\u201338:31 (2018). \n                    https:\/\/doi.org\/10.1145\/3196276","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"614_CR4","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/2344422.2344428","volume":"8","author":"D Binkele-Raible","year":"2012","unstructured":"Binkele-Raible, D., Fernau, H., Fomin, F.V., Lokshtanov, D., Saurabh, S., Villanger, Y.: Kernel(s) for problems with no kernel: on out-trees with many leaves. ACM Trans. Algorithms 8(4), 38 (2012). \n                    https:\/\/doi.org\/10.1145\/2344422.2344428","journal-title":"ACM Trans. Algorithms"},{"key":"614_CR5","unstructured":"Bodlaender, H.L., Demaine, E.D., Fellows, M.R., Guo, J., Hermelin, D., Lokshtanov, D., M\u00fcller, M., Raman, V., Rooij, J.V., Rosamond, F.A.: Open problems in parameterized and exact computation\u2014IWPEC 2008. Technical Report UU-CS-2008-017, Utrecht University (2008)"},{"issue":"1","key":"614_CR6","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014). \n                    https:\/\/doi.org\/10.1137\/120880240","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"614_CR7","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1137\/050633263","volume":"36","author":"G Chen","year":"2006","unstructured":"Chen, G., Gao, Z., Yu, X., Zang, W.: Approximating longest cycles in graphs with bounded degrees. SIAM J. Comput. 36(3), 635\u2013656 (2006). \n                    https:\/\/doi.org\/10.1137\/050633263","journal-title":"SIAM J. Comput."},{"issue":"1","key":"614_CR8","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1006\/jctb.2002.2113","volume":"86","author":"G Chen","year":"2002","unstructured":"Chen, G., Yu, X.: Long cycles in 3-connected graphs. J. Comb. Theory Ser. B 86(1), 80\u201399 (2002). \n                    https:\/\/doi.org\/10.1006\/jctb.2002.2113","journal-title":"J. Comb. Theory Ser. B"},{"issue":"6","key":"614_CR9","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1016\/j.jctb.2012.07.003","volume":"102","author":"G Chen","year":"2012","unstructured":"Chen, G., Yu, X., Zang, W.: The circumference of a graph with no $$K_{3, t}$$-minor, II. J. Comb. Theory Ser. B 102(6), 1211\u20131240 (2012). \n                    https:\/\/doi.org\/10.1016\/j.jctb.2012.07.003","journal-title":"J. Comb. Theory Ser. B"},{"key":"614_CR10","doi-asserted-by":"crossref","unstructured":"Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Minimum bisection is fixed parameter tractable. In: Proceedings of STOC 2014, pp. 323\u2013332. ACM (2014). \n                    https:\/\/doi.org\/10.1145\/2591796.2591852","DOI":"10.1145\/2591796.2591852"},{"key":"614_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory, 4th edn. Springer, Heidelberg (2010)","edition":"4"},{"issue":"6","key":"614_CR12","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1016\/j.jctb.2012.07.001","volume":"102","author":"R Diestel","year":"2012","unstructured":"Diestel, R., Kawarabayashi, K., M\u00fcller, T., Wollan, P.: On the excluded minor structure theorem for graphs of large tree-width. J. Comb. Theory Ser. B 102(6), 1189\u20131210 (2012). \n                    https:\/\/doi.org\/10.1016\/j.jctb.2012.07.001","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"614_CR13","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1112\/plms\/s3-2.1.69","volume":"s3\u20132","author":"GA Dirac","year":"1952","unstructured":"Dirac, G.A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. s3\u20132(1), 69\u201381 (1952). \n                    https:\/\/doi.org\/10.1112\/plms\/s3-2.1.69","journal-title":"Proc. Lond. Math. Soc."},{"issue":"6","key":"614_CR14","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1016\/j.jctb.2011.02.002","volume":"101","author":"J Fr\u00f6hlich","year":"2011","unstructured":"Fr\u00f6hlich, J., M\u00fcller, T.: Linear connectivity forces large complete bipartite minors: an alternative approach. J. Comb. Theory Ser. B 101(6), 502\u2013508 (2011). \n                    https:\/\/doi.org\/10.1016\/j.jctb.2011.02.002","journal-title":"J. Comb. Theory Ser. B"},{"key":"614_CR15","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.jcss.2016.09.002","volume":"84","author":"J Gajarsk\u00fd","year":"2017","unstructured":"Gajarsk\u00fd, J., Hlinen\u00fd, P., Obdrz\u00e1lek, J., Ordyniak, S., Reidl, F., Rossmanith, P., Villaamil, F.S., Sikdar, S.: Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci. 84, 219\u2013242 (2017). \n                    https:\/\/doi.org\/10.1016\/j.jcss.2016.09.002","journal-title":"J. Comput. Syst. Sci."},{"key":"614_CR16","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2016.02.001","volume":"622","author":"V Garnero","year":"2016","unstructured":"Garnero, V., Weller, M.: Parameterized certificate dispersal and its variants. Theor. Comput. Sci. 622, 66\u201378 (2016). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2016.02.001","journal-title":"Theor. Comput. Sci."},{"key":"614_CR17","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2016.04.034","volume":"636","author":"ED Giacomo","year":"2016","unstructured":"Giacomo, E.D., Liotta, G., Mchedlidze, T.: Lower and upper bounds for long induced paths in 3-connected planar graphs. Theor. Comput. Sci. 636, 47\u201355 (2016). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2016.04.034","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"614_CR18","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1137\/120892234","volume":"44","author":"M Grohe","year":"2015","unstructured":"Grohe, M., Marx, D.: Structure theorem and isomorphism test for graphs with excluded topological subgraphs. SIAM J. Comput. 44(1), 114\u2013159 (2015). \n                    https:\/\/doi.org\/10.1137\/120892234","journal-title":"SIAM J. Comput."},{"issue":"3","key":"614_CR19","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1007\/s00453-014-9910-8","volume":"71","author":"D Hermelin","year":"2015","unstructured":"Hermelin, D., Kratsch, S., Soltys, K., Wahlstr\u00f6m, M., Wu, X.: A completeness theory for polynomial (Turing) kernelization. Algorithmica 71(3), 702\u2013730 (2015). \n                    https:\/\/doi.org\/10.1007\/s00453-014-9910-8","journal-title":"Algorithmica"},{"key":"614_CR20","doi-asserted-by":"crossref","unstructured":"H\u00fcffner, F., Komusiewicz, C., Sorge, M.: Finding highly connected subgraphs. In: Proceedings of 41st SOFSEM, pp. 254\u2013265 (2015). \n                    https:\/\/doi.org\/10.1007\/978-3-662-46078-8_21","DOI":"10.1007\/978-3-662-46078-8_21"},{"key":"614_CR21","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.jcss.2016.10.008","volume":"85","author":"BMP Jansen","year":"2017","unstructured":"Jansen, B.M.P.: Turing kernelization for finding long paths and cycles in restricted graph classes. J. Comput. Syst. Sci. 85, 18\u201337 (2017). \n                    https:\/\/doi.org\/10.1016\/j.jcss.2016.10.008","journal-title":"J. Comput. Syst. Sci."},{"key":"614_CR22","doi-asserted-by":"crossref","unstructured":"Jansen, B.M.P., Marx, D.: Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels. In: Proceedings of 26th SODA, pp. 616\u2013629 (2015). \n                    https:\/\/doi.org\/10.1137\/1.9781611973730.42","DOI":"10.1137\/1.9781611973730.42"},{"key":"614_CR23","unstructured":"Kolay, S., Panolan, F.: Parameterized algorithms for deletion to $$(r, \\ell )$$-graphs. In: Proceedings of 35th FSTTCS, pp. 420\u2013433 (2015). \n                    https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2015.420"},{"key":"614_CR24","unstructured":"Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Manuscript (2019)"},{"key":"614_CR25","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol.\u00a028. Springer, Berlin (2012). \n                    https:\/\/doi.org\/10.1007\/978-3-642-27875-4","DOI":"10.1007\/978-3-642-27875-4"},{"issue":"1","key":"614_CR26","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. V. Excluding a planar graph. J. Comb. Theory Ser. B 41(1), 92\u2013114 (1986). \n                    https:\/\/doi.org\/10.1016\/0095-8956(86)90030-4","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"614_CR27","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory Ser. B 52(2), 153\u2013190 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"614_CR28","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1006\/jctb.1999.1919","volume":"77","author":"N Robertson","year":"1999","unstructured":"Robertson, N., Seymour, P.D.: Graph minors: XVII. Taming a vortex. J. Comb. Theory Ser. B 77(1), 162\u2013210 (1999). \n                    https:\/\/doi.org\/10.1006\/jctb.1999.1919","journal-title":"J. Comb. Theory Ser. B"},{"issue":"5","key":"614_CR29","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s11590-011-0311-5","volume":"6","author":"A Sch\u00e4fer","year":"2012","unstructured":"Sch\u00e4fer, A., Komusiewicz, C., Moser, H., Niedermeier, R.: Parameterized computational complexity of finding small-diameter subgraphs. Optim. Lett. 6(5), 883\u2013891 (2012). \n                    https:\/\/doi.org\/10.1007\/s11590-011-0311-5","journal-title":"Optim. Lett."},{"key":"614_CR30","unstructured":"Shan, S.: Homeomorphically irreducible spanning trees, Halin graphs, and long cycles in 3-connected graphs with bounded maximum degrees. Ph.D. thesis, Georgia State University (2015). \n                    http:\/\/scholarworks.gsu.edu\/math_diss\/23\/\n                    \n                  . Accessed 5 Nov 2015"},{"issue":"3","key":"614_CR31","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/s00453-015-0083-x","volume":"77","author":"S Thomass\u00e9","year":"2017","unstructured":"Thomass\u00e9, S., Trotignon, N., Vuskovic, K.: A polynomial turing-kernel for weighted independent set in bull-free graphs. Algorithmica 77(3), 619\u2013641 (2017). \n                    https:\/\/doi.org\/10.1007\/s00453-015-0083-x","journal-title":"Algorithmica"},{"key":"614_CR32","doi-asserted-by":"crossref","DOI":"10.3138\/9781487584863","volume-title":"Connectivity in Graphs. Mathematical expositions","author":"WT Tutte","year":"1966","unstructured":"Tutte, W.T.: Connectivity in Graphs. Mathematical expositions. University of Toronto Press, Toronto (1966)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00614-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00614-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00614-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,1]],"date-time":"2020-08-01T23:05:49Z","timestamp":1596323149000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00614-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,3]]},"references-count":32,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["614"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00614-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,8,3]]},"assertion":[{"value":"6 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}