{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:48:42Z","timestamp":1764784122765},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,8,23]],"date-time":"2018-08-23T00:00:00Z","timestamp":1534982400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00453-018-0495-5","type":"journal-article","created":{"date-parts":[[2018,8,23]],"date-time":"2018-08-23T09:07:42Z","timestamp":1535015262000},"page":"1615-1656","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Explicit Linear Kernels for Packing Problems"],"prefix":"10.1007","volume":"81","author":[{"given":"Valentin","family":"Garnero","sequence":"first","affiliation":[]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,23]]},"reference":[{"key":"495_CR1","doi-asserted-by":"crossref","unstructured":"Abrahamson, K.R., Fellows, M.R.: Finite automata, bounded treewidth, and well-quasiordering. In: Proceedings of Graph Structure Theory, Contemporary Mathematics, vol. 147, pp. 539\u2013564. American Mathematical Society (1991)","DOI":"10.1090\/conm\/147\/01199"},{"issue":"50","key":"495_CR2","doi-asserted-by":"publisher","first-page":"7018","DOI":"10.1016\/j.tcs.2011.09.015","volume":"412","author":"I Adler","year":"2011","unstructured":"Adler, I., Dorn, F., Fomin, F.V., Sau, I., Thilikos, D.M.: Faster parameterized algorithms for minor containment. Theor. Comput. Sci. 412(50), 7018\u20137028 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"495_CR3","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1016\/j.jctb.2016.10.001","volume":"122","author":"I Adler","year":"2017","unstructured":"Adler, I., Kolliopoulos, S.G., Krause, P.K., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Irrelevant vertices for the planar disjoint paths problem. J. Comb. Theory Ser. B 122, 815\u2013843 (2017)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"495_CR4","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J Alber","year":"2004","unstructured":"Alber, J., Fellows, M., Niedermeier, R.: Polynomial-time data reduction for dominating set. J. ACM 51(3), 363\u2013384 (2004)","journal-title":"J. ACM"},{"issue":"5","key":"495_CR5","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/174147.169807","volume":"40","author":"S Arnborg","year":"1993","unstructured":"Arnborg, S., Courcelle, B., Proskurowski, A., Seese, D.: An algebraic theory of graph reduction. J. ACM 40(5), 1134\u20131164 (1993)","journal-title":"J. ACM"},{"key":"495_CR6","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.tcs.2016.07.021","volume":"647","author":"A Atminas","year":"2016","unstructured":"Atminas, A., Kaminski, M., Raymond, J.-F.: Scattered packings of cycles. Theor. Comput. Sci. 647, 33\u201342 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"495_CR7","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"495_CR8","doi-asserted-by":"publisher","first-page":"44:1","DOI":"10.1145\/2973749","volume":"63","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (meta) kernelization. J. ACM 63(5), 44:1\u201344:69 (2016)","journal-title":"J. ACM"},{"issue":"35","key":"495_CR9","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"495_CR10","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1006\/inco.2000.2958","volume":"167","author":"HL Bodlaender","year":"2001","unstructured":"Bodlaender, H.L., van Antwerpen-de Fluiter, B.: Reduction algorithms for graphs of small treewidth. Inf. Comput. 167(2), 86\u2013119 (2001)","journal-title":"Inf. Comput."},{"key":"495_CR11","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"RB Borie","year":"1992","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algo- rithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7, 555\u2013581 (1992)","journal-title":"Algorithmica"},{"key":"495_CR12","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"JR B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: Weak second order arithmetic and finite automata. Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik 6, 66\u201392 (1960)","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"key":"495_CR13","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Chuzhoy, J.: Large-treewidth graph decompositions and applications. In: Proceedings of the 45th Symposium on the Theory of Computing (STOC), pp. 291\u2013300 (2013)","DOI":"10.1145\/2488608.2488645"},{"key":"495_CR14","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Chuzhoy, J.: Polynomial bounds for the grid-minor theorem. In: Proceedings of the 46th ACM Symposium on the Theory of Computing (STOC), pp. 60\u201369 (2014)","DOI":"10.1145\/2591796.2591813"},{"issue":"1","key":"495_CR15","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"495_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., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"495_CR17","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: Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 150\u2013159. IEEE Computer Society (2011)","DOI":"10.1109\/FOCS.2011.23"},{"issue":"1","key":"495_CR18","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00493-008-2140-4","volume":"28","author":"ED Demaine","year":"2008","unstructured":"Demaine, E.D., Hajiaghayi, M.: Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica 28(1), 19\u201336 (2008)","journal-title":"Combinatorica"},{"key":"495_CR19","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, vol. 173, 4th edn. Springer, Berlin (2010)","edition":"4"},{"key":"495_CR20","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1965-035-8","volume":"17","author":"P Erd\u0151s","year":"1965","unstructured":"Erd\u0151s, P., P\u00f3sa, L.: On independent circuits contained in a graph. Can. J. Math. 17, 347\u2013352 (1965)","journal-title":"Can. J. Math."},{"issue":"1","key":"495_CR21","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.disopt.2010.09.006","volume":"8","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., Guo, J., Komusiewicz, C., Niedermeier, R., Uhlmann, J.: Graph-based data clustering with overlaps. Discrete Optim. 8(1), 2\u201317 (2011)","journal-title":"Discrete Optim."},{"key":"495_CR22","doi-asserted-by":"crossref","unstructured":"Fellows, M.R., Langston, M.A.: An analogue of the Myhill\u2013Nerode theorem and its use in computing finite-basis characterizations (extended abstract). In: Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 520\u2013525 (1989)","DOI":"10.1109\/SFCS.1989.63528"},{"issue":"3","key":"495_CR23","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1016\/S0022-0000(05)80079-0","volume":"49","author":"MR Fellows","year":"1994","unstructured":"Fellows, M.R., Langston, M.A.: On search, decision, and the efficiency of polynomial-time algorithms. J. Comput. Syst. Sci. 49(3), 769\u2013779 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"495_CR24","doi-asserted-by":"crossref","unstructured":"Fernau, H., L\u00f3pez-Ortiz, A., Romero, J.: Kernelization algorithms for packing problems allowing overlaps. In: Proceedings of the 12th Annual Conference on Theory and Applications of Models of Computation, (TAMC), volume 9076 of LNCS, pp. 415\u2013427 (2015)","DOI":"10.1007\/978-3-319-17142-5_35"},{"issue":"5","key":"495_CR25","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/j.jctb.2011.02.008","volume":"101","author":"FV Fomin","year":"2011","unstructured":"Fomin, F.V., Golovach, P.A., Thilikos, D.M.: Contraction obstructions for treewidth. J. Comb. Theory Ser. B 101(5), 302\u2013314 (2011)","journal-title":"J. Comb. Theory Ser. B"},{"key":"495_CR26","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Bidimensionality and EPTAS. In: Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 748\u2013759 (2011)","DOI":"10.1137\/1.9781611973082.59"},{"key":"495_CR27","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 503\u2013510 (2010)","DOI":"10.1137\/1.9781611973075.43"},{"issue":"3","key":"495_CR28","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1002\/jgt.20503","volume":"66","author":"FV Fomin","year":"2011","unstructured":"Fomin, F.V., Saurabh, S., Thilikos, D.M.: Strengthening Erd\u0151s\u2013P\u00f3sa property for minor-closed graph classes. J. Gr. Theory 66(3), 235\u2013240 (2011)","journal-title":"J. Gr. Theory"},{"issue":"4","key":"495_CR29","doi-asserted-by":"publisher","first-page":"1864","DOI":"10.1137\/140968975","volume":"29","author":"V Garnero","year":"2015","unstructured":"Garnero, V., Paul, C., Sau, I., Thilikos, D.M.: Explicit linear kernels via dynamic programming. SIAM J. Discrete Math. 29(4), 1864\u20131894 (2015)","journal-title":"SIAM J. Discrete Math."},{"key":"495_CR30","unstructured":"Giannopoulou, A.: Partial Orderings and Algorithms on Graphs. PhD thesis, Department of Mathematics, University of Athens, Greece (2012)"},{"key":"495_CR31","doi-asserted-by":"crossref","unstructured":"Guo, J., Niedermeier, R.: Linear problem kernels for NP-hard problems on planar graphs. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP), volume 4596 of LNCS, pp. 375\u2013386 (2007)","DOI":"10.1007\/978-3-540-73420-8_34"},{"key":"495_CR32","unstructured":"Jim Geelen, J., Huynh, T., Richter, R.B.: Explicit bounds for graph minors. CoRR (2013). \n                    arXiv:1305.1451"},{"key":"495_CR33","unstructured":"Kawarabayashi, K., Kobayashi, Y.: Linear min\u2013max relation between the treewidth of \n                    \n                      \n                    \n                    $$H$$\n                    \n                      \n                        H\n                      \n                    \n                  -minor-free graphs and its largest grid. In: Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS), volume\u00a014 of LIPIcs, pp. 278\u2013289 (2012)"},{"key":"495_CR34","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Wollan, P.: A simpler algorithm and shorter proof for the graph minor decomposition. In: Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pp. 451\u2013458 (2011)","DOI":"10.1145\/1993636.1993697"},{"issue":"2","key":"495_CR35","first-page":"21","volume":"12","author":"EJ Kim","year":"2016","unstructured":"Kim, E.J., Langer, A., Paul, C., Reidl, F., Rossmanith, P., Sau, I., Sikdar, S.: Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Trans. Algorithms 12(2), 21 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"495_CR36","volume-title":"Treewidth. Computations and Approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. Computations and Approximations. Springer, Berlin (1994)"},{"key":"495_CR37","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":"495_CR38","unstructured":"Mazoit, F.: A single exponential bound for the redundant vertex theorem on surfaces. CoRR (2013). \n                    arXiv:1309.7820"},{"key":"495_CR39","doi-asserted-by":"crossref","unstructured":"Moser, H.: A problem kernelization for graph packing. In: Proceedings of the 35th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), volume 5404 of LNCS, pp. 401\u2013412 (2009)","DOI":"10.1007\/978-3-540-95891-8_37"},{"issue":"1","key":"495_CR40","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)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"495_CR41","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"495_CR42","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","volume":"89","author":"N Robertson","year":"2003","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XVI. excluding a non-planar graph. J. Comb. Theory Ser. B 89(1), 43\u201376 (2003)","journal-title":"J. Comb. Theory Ser. B"},{"key":"495_CR43","doi-asserted-by":"crossref","unstructured":"Romero, J., L\u00f3pez-Ortiz, A.: The \n                    \n                      \n                    \n                    $${\\cal{G}}$$\n                    \n                      \n                        G\n                      \n                    \n                  -packing with \n                    \n                      \n                    \n                    $$t$$\n                    \n                      \n                        t\n                      \n                    \n                  -overlap problem. In: Proceedings of the 8th International Workshop on Algorithms and Computation (WALCOM), volume 8344 of LNCS, pp. 114\u2013124 (2014)","DOI":"10.1007\/978-3-319-04657-0_13"},{"key":"495_CR44","doi-asserted-by":"crossref","unstructured":"Romero, J., L\u00f3pez-Ortiz, A.: A parameterized algorithm for packing overlapping subgraphs. In: Proceedings of the 9th International Computer Science Symposium in Russia (CSR), volume 8476 of LNCS, pp. 325\u2013336 (2014)","DOI":"10.1007\/978-3-319-06686-8_25"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0495-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0495-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0495-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,22]],"date-time":"2019-08-22T19:04:42Z","timestamp":1566500682000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0495-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,23]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["495"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0495-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,23]]},"assertion":[{"value":"19 October 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}