{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:54Z","timestamp":1740109254417,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,11,15]],"date-time":"2016-11-15T00:00:00Z","timestamp":1479168000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["12 JS02 002 01"],"award-info":[{"award-number":["12 JS02 002 01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2013\/09\/B\/ST6\/03136"],"award-info":[{"award-number":["2013\/09\/B\/ST6\/03136"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,9]]},"DOI":"10.1007\/s00453-016-0244-6","type":"journal-article","created":{"date-parts":[[2016,11,15]],"date-time":"2016-11-15T09:07:37Z","timestamp":1479200857000},"page":"159-188","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Linear Kernels for Outbranching Problems in Sparse Digraphs"],"prefix":"10.1007","volume":"79","author":[{"given":"Marthe","family":"Bonamy","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7546-2969","authenticated-orcid":false,"given":"\u0141ukasz","family":"Kowalik","sequence":"additional","affiliation":[]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[]},{"given":"Arkadiusz","family":"Soca\u0142a","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,11,15]]},"reference":[{"issue":"3","key":"244_CR1","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J Alber","year":"2004","unstructured":"Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for dominating set. J. ACM 51(3), 363\u2013384 (2004)","journal-title":"J. ACM"},{"issue":"4","key":"244_CR2","doi-asserted-by":"crossref","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)","journal-title":"ACM Trans. Algorithms"},{"key":"244_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In: ICALP 2013. Lecture Notes in Computer Science, vol. 7965, pp. 196\u2013207. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-39206-1_17"},{"key":"244_CR4","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: An $${O}(c^k n)$$ O ( c k n ) 5-approximation algorithm for treewidth. In: FOCS 2013, pp. 499\u2013508. IEEE Computer Society (2013)","DOI":"10.1109\/FOCS.2013.60"},{"key":"244_CR5","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25\u201327, 2009, Atlanta, Georgia, USA, pp. 629\u2013638. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.46"},{"key":"244_CR6","unstructured":"Bonamy, M., Kowalik, \u0141., Pilipczuk, M., Soca\u0142a, A.: Linear kernels for outbranching problems in sparse digraphs. In: 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16\u201318, 2015, Patras, Greece, Volume 43 of LIPIcs, pp. 199\u2013211. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)"},{"key":"244_CR7","unstructured":"Chor, B., Fellows, M., Juedes, D.W.: Linear kernels in linear time, or how to save k colors in o(n $$^{2}$$ 2 ) steps. In: Graph-Theoretic Concepts in Computer Science, 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21\u201323, 2004, Revised Papers, pp. 257\u2013269 (2004)"},{"key":"244_CR8","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22\u201325, 2011, pp. 150\u2013159. IEEE Computer Society (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"244_CR9","doi-asserted-by":"crossref","unstructured":"Daligault, J., Thomass\u00e9, S.: On finding directed trees with many leaves. In: Chen, J., Fomin, F.V. (eds.) Parameterized and Exact Computation, pp. 86\u201397. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-11269-0_7"},{"issue":"13","key":"244_CR10","doi-asserted-by":"crossref","first-page":"3000","DOI":"10.1016\/j.dam.2009.04.012","volume":"157","author":"P Dankelmann","year":"2009","unstructured":"Dankelmann, P., Gutin, G., Kim, E.J.: On complexity of minimum leaf out-branching problem. Discrete Appl. Math. 157(13), 3000\u20133004 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"244_CR11","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and $$h$$ h -minor-free graphs. J. ACM 52(6), 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"244_CR12","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M., Kawarabayashi, K.: Contraction decomposition in $$h$$ h -minor-free graphs and algorithmic applications. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6\u20138 June 2011, pp. 441\u2013450. ACM (2011)","DOI":"10.1145\/1993636.1993696"},{"key":"244_CR13","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.ic.2013.11.006","volume":"233","author":"F Dorn","year":"2013","unstructured":"Dorn, F., Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Beyond bidimensionality: parameterized subexponential algorithms on directed graphs. Inf. Comput. 233, 60\u201370 (2013)","journal-title":"Inf. Comput."},{"issue":"1\u20133","key":"244_CR14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0012-365X(92)90130-8","volume":"105","author":"RJ Douglas","year":"1992","unstructured":"Douglas, R.J.: NP-completeness and degree restricted spanning trees. Discrete Math. 105(1\u20133), 41\u201347 (1992)","journal-title":"Discrete Math."},{"key":"244_CR15","unstructured":"Drange, P.G., Dregi, M.S., Fomin, F.V., Kreutzer, S., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Reidl, F., Villaamil, F.S., Saurabh, S., Siebertz, S., Sikdar, S.: Kernelization and sparseness: the case of dominating set. In: 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17\u201320, 2016, Orl\u00e9ans, France, Volume 47 of LIPIcs, pp. 31:1\u201331:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)"},{"key":"244_CR16","doi-asserted-by":"crossref","unstructured":"Fellows, M., Heggernes, P., Rosamond, F.A., Sloper, C., Telle, J.A.: Finding $$k$$ k disjoint triangles in an arbitrary graph. In: Graph-Theoretic Concepts in Computer Science, 30th International Workshop,WG 2004, Bad Honnef, Germany, June 21\u201323, 2004, Revised Papers, Volume 3353 of Lecture Notes in Computer Science, pp. 235\u2013244. Springer (2004)","DOI":"10.1007\/978-3-540-30559-0_20"},{"key":"244_CR17","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer, Berlin (2006)"},{"issue":"16","key":"244_CR18","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1016\/j.ipl.2011.05.016","volume":"111","author":"FV Fomin","year":"2011","unstructured":"Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Subexponential algorithms for partial cover problems. Inf. Process. Lett. 111(16), 814\u2013818 (2011)","journal-title":"Inf. Process. Lett."},{"key":"244_CR19","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: SODA, pp. 503\u2013510 (2010)","DOI":"10.1137\/1.9781611973075.43"},{"key":"244_CR20","doi-asserted-by":"crossref","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. In: Bodlaender, H.L., Italiano, G.F. (eds.), ESA 2013, Volume 8125 of Lecture Notes in Computer Science, pp. 529\u2013540. Springer (2013)","DOI":"10.1007\/978-3-642-40450-4_45"},{"key":"244_CR21","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem in NP-complete. SIAM J. Appl. Math. 32, 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"issue":"4","key":"244_CR22","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/s00493-003-0037-9","volume":"23","author":"M Grohe","year":"2003","unstructured":"Grohe, M.: Local tree-width, excluded minors, approximation algorithms. Combinatorica 23(4), 613\u2013632 (2003)","journal-title":"Combinatorica"},{"issue":"45","key":"244_CR23","doi-asserted-by":"crossref","first-page":"4571","DOI":"10.1016\/j.tcs.2009.03.036","volume":"410","author":"G Gutin","year":"2009","unstructured":"Gutin, G., Razgon, I., Kim, E.J.: Minimum leaf out-branching and related problems. Theor. Comput. Sci. 410(45), 4571\u20134579 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"244_CR24","doi-asserted-by":"crossref","unstructured":"Klein, P.N., Marx, D.: A subexponential parameterized algorithm for subset TSP on planar graphs. In: Chekuri, C. (ed.), Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5\u20137, 2014, pp. 1812\u20131830. SIAM (2014)","DOI":"10.1137\/1.9781611973402.131"},{"key":"244_CR25","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"key":"244_CR26","unstructured":"Lokshtanov, D., Saurabh, S., Wahlstr\u00f6m, M.: Subexponential parameterized odd cycle transversal on planar graphs. In: D\u2019Souza, D., Kavitha, T., Radhakrishnan, J. (eds.), IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15\u201317, 2012, Hyderabad, India, Volume 18 of LIPIcs, pp. 424\u2013434. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)"},{"key":"244_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity: Graphs, Structures, and Algorithms, Volume 28 of Algorithms and Combinatorics","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity: Graphs, Structures, and Algorithms, Volume 28 of Algorithms and Combinatorics. Springer, Berlin (2012)"},{"key":"244_CR28","doi-asserted-by":"crossref","unstructured":"Pilipczuk, M.: Problems parameterized by treewidth tractable in single exponential time: a logical approach. In: MFCS 2011, Volume 6907 of Lecture Notes in Computer Science, pp. 520\u2013531. Springer (2011)","DOI":"10.1007\/978-3-642-22993-0_47"},{"key":"244_CR29","unstructured":"Pilipczuk, M.: Problems parameterized by treewidth tractable in single exponential time: a logical approach. CoRR (2011) arXiv:abs\/1104.3057"},{"key":"244_CR30","unstructured":"Pilipczuk, M., Pilipczuk, M., Sankowski, P., van Leeuwen, E.J.: Subexponential-time parameterized algorithm for Steiner tree on planar graphs. In: Portier, N., Wilke, T. (eds.), 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27\u2013March 2, 2013, Kiel, Germany, Volume 20 of LIPIcs, pp. 353\u2013364. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013)"},{"key":"244_CR31","doi-asserted-by":"crossref","unstructured":"Pilipczuk, M., Pilipczuk, M., Sankowski, P., van Leeuwen, E.J.: Network sparsification for Steiner problems on planar and bounded-genus graphs. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18\u201321, 2014, pp. 276\u2013285. IEEE Computer Society (2014)","DOI":"10.1109\/FOCS.2014.37"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0244-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0244-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0244-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,15]],"date-time":"2019-09-15T12:11:46Z","timestamp":1568549506000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0244-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,15]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["244"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0244-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,11,15]]}}}