{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:14Z","timestamp":1781078174255,"version":"3.54.1"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2022,4,19]],"date-time":"2022-04-19T00:00:00Z","timestamp":1650326400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,4,19]],"date-time":"2022-04-19T00:00:00Z","timestamp":1650326400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s00453-022-00965-5","type":"journal-article","created":{"date-parts":[[2022,4,19]],"date-time":"2022-04-19T17:02:53Z","timestamp":1650387773000},"page":"3300-3337","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Twin-width and Polynomial Kernels"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1653-5822","authenticated-orcid":false,"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6824-0516","authenticated-orcid":false,"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8108-4036","authenticated-orcid":false,"given":"Amadeus","family":"Reinald","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6243-5910","authenticated-orcid":false,"given":"R\u00e9mi","family":"Watrigant","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,4,19]]},"reference":[{"issue":"3","key":"965_CR1","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1145\/990308.990309","journal-title":"J. ACM"},{"issue":"4","key":"965_CR2","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/s00453-008-9204-0","volume":"54","author":"N Alon","year":"2009","unstructured":"Alon, N., Gutner, S.: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica 54(4), 544\u2013556 (2009). https:\/\/doi.org\/10.1007\/s00453-008-9204-0","journal-title":"Algorithmica"},{"issue":"8","key":"965_CR3","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","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","journal-title":"J. Comput. Syst. Sci."},{"key":"965_CR4","doi-asserted-by":"publisher","unstructured":"Bonnet, \u00c9., Geniet, C., Kim, E.J., Thomass\u00e9, S., Watrigant, R.: Twin-width II: small classes. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1977\u20131996 (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.118","DOI":"10.1137\/1.9781611976465.118"},{"key":"965_CR5","doi-asserted-by":"publisher","unstructured":"Bonnet, \u00c9., Geniet, C., Kim, E. J., Thomass\u00e9, S., Watrigant, R.: Twin-width III: max independent set, min dominating set, and coloring. In: Bansal, N., Merelli, E., Worrell, J., (eds), 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 35:1\u201335:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik. https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2021\/14104, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.35","DOI":"10.4230\/LIPIcs.ICALP.2021.35"},{"key":"965_CR6","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Giocanti, U., Ossona de Mendez, P., Simon, P., Thomass\u00e9, S., Toru\u0144czyk, S.: Twin-width IV: ordered graphs and matrices. CoRR, abs\/2102.03117, 2021. arXiv:2102.03117","DOI":"10.1145\/3519935.3520037"},{"key":"965_CR7","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Kim, E. J., Reinald, A., Thomass\u00e9, S.: Twin-width VI: the lens of contraction sequences. In: Proceedings of the Thirty Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Alexandria, Virginia, USA (online), January 9\u201312, 2022 (2022)","DOI":"10.1137\/1.9781611977073.45"},{"key":"965_CR8","doi-asserted-by":"publisher","unstructured":"Bonnet, \u00c9., Kim, E.\u00a0J., Thomass\u00e9, S. Watrigant, R.: Twin-width I: tractable FO model checking. J. ACM, 69(1), 3:1\u20133:46 (2022). https:\/\/doi.org\/10.1145\/3486655","DOI":"10.1145\/3486655"},{"issue":"1","key":"965_CR9","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s00224-013-9478-8","volume":"54","author":"N Bousquet","year":"2014","unstructured":"Bousquet, N., Gon\u00e7alves, D., Mertzios, G.B., Paul, C., Sau, I., Thomass\u00e9, S.: Parameterized domination in circle graphs. Theory Comput. Syst. 54(1), 45\u201372 (2014). https:\/\/doi.org\/10.1007\/s00224-013-9478-8","journal-title":"Theory Comput. Syst."},{"key":"965_CR10","doi-asserted-by":"publisher","unstructured":"Chan, T.\u00a0M., Grant, E., K\u00f6nemann, J., Sharpe, M.: Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In: Rabani, Y., (ed) Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17\u201319, 2012, pp. 1576\u20131585. SIAM (2012). https:\/\/doi.org\/10.1137\/1.9781611973099.125","DOI":"10.1137\/1.9781611973099.125"},{"issue":"4","key":"965_CR11","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1137\/050646354","volume":"37","author":"J Chen","year":"2007","unstructured":"Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SIAM J. Comput. 37(4), 1077\u20131106 (2007). https:\/\/doi.org\/10.1137\/050646354","journal-title":"SIAM J. Comput."},{"issue":"8","key":"965_CR12","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346\u20131367 (2006). https:\/\/doi.org\/10.1016\/j.jcss.2006.04.007","journal-title":"J. Comput. Syst. Sci."},{"key":"965_CR13","unstructured":"Cibulka, J., Kyncl, J.: F\u00fcredi-Hajnal limits are typically subexponential. CoRR, abs\/1607.07491, (2016). arXiv:1607.07491"},{"issue":"1\u20133","key":"965_CR14","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discret. Math. 86(1\u20133), 165\u2013177 (1990). https:\/\/doi.org\/10.1016\/0012-365X(90)90358-O","journal-title":"Discret. Math."},{"issue":"2","key":"965_CR15","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000). https:\/\/doi.org\/10.1007\/s002249910009","journal-title":"Theory Comput. Syst."},{"key":"965_CR16","doi-asserted-by":"publisher","unstructured":"Cygan, M.: Deterministic parameterized connected vertex cover. In: Fomin, F. V., Kaski,, P., (eds) Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4\u20136, 2012. Proceedings, volume 7357 of Lecture Notes in Computer Science, pp. 95\u2013106. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-31155-0_9","DOI":"10.1007\/978-3-642-31155-0_9"},{"key":"965_CR17","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F. V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, vol.\u00a04. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"3","key":"965_CR18","doi-asserted-by":"publisher","first-page":"43:1","DOI":"10.1145\/3108239","volume":"13","author":"M Cygan","year":"2017","unstructured":"Cygan, M., Grandoni, F., Hermelin, D.: Tight kernel bounds for problems on graphs with small degeneracy. ACM Trans. Algorithms 13(3), 43:1-43:22 (2017). https:\/\/doi.org\/10.1145\/3108239","journal-title":"ACM Trans. Algorithms"},{"issue":"50","key":"965_CR19","doi-asserted-by":"publisher","first-page":"6982","DOI":"10.1016\/j.tcs.2011.09.010","volume":"412","author":"M Cygan","year":"2011","unstructured":"Cygan, M., Philip, G., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Dominating set is fixed parameter tractable in claw-free graphs. Theor. Comput. Sci. 412(50), 6982\u20137000 (2011). https:\/\/doi.org\/10.1016\/j.tcs.2011.09.010","journal-title":"Theor. Comput. Sci."},{"issue":"15","key":"965_CR20","doi-asserted-by":"publisher","first-page":"2131","DOI":"10.1016\/j.dam.2012.05.016","volume":"160","author":"M Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Kernelization hardness of connectivity problems in d-degenerate graphs. Discrete Appl. Math. 160(15), 2131\u20132141 (2012). https:\/\/doi.org\/10.1016\/j.dam.2012.05.016","journal-title":"Discrete Appl. Math."},{"key":"965_CR21","doi-asserted-by":"publisher","unstructured":"Dawar, A., Kreutzer, S.: Domination problems in nowhere-dense classes. In: Kannan, R., Narayan Kumar, K., (eds) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, December 15\u201317, 2009, IIT Kanpur, India, vol.\u00a04 of LIPIcs, pp. 157\u2013168. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2009). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2009.2315","DOI":"10.4230\/LIPIcs.FSTTCS.2009.2315"},{"issue":"6","key":"965_CR22","doi-asserted-by":"publisher","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-minor-free graphs. J. ACM 52(6), 866\u2013893 (2005). https:\/\/doi.org\/10.1145\/1101821.1101823","journal-title":"J. ACM"},{"issue":"2","key":"965_CR23","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/2650261","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and IDs. ACM Trans. Algorithms 11(2), 13:1-13:20 (2014). https:\/\/doi.org\/10.1145\/2650261","journal-title":"ACM Trans. Algorithms"},{"key":"965_CR24","doi-asserted-by":"publisher","unstructured":"Dorn, F.: Dynamic programming and fast matrix multiplication. In: Azar, Y., Erlebach, T., editors, Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11\u201313, 2006, Proceedings, vol. 4168 of Lecture Notes in Computer Science, pp. 280\u2013291. Springer (2006). https:\/\/doi.org\/10.1007\/11841036_27","DOI":"10.1007\/11841036_27"},{"key":"965_CR25","doi-asserted-by":"publisher","unstructured":"Downey, R. G., Fellows, M. R.: Fundamentals of parameterized complexity. Texts in Computer Science. Springer, Berlin (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"965_CR26","doi-asserted-by":"publisher","unstructured":"Drange, P.\u00a0G., Dregi, M.\u00a0S., Fomin, F. V., Kreutzer, S., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Reidl, F., Villaamil, F.\u00a0S., Saurabh, S., Siebertz, S., Sikdar, S.: Kernelization and sparseness: the case of dominating set. In: Ollinger, N., Vollmer, H., (eds) 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17\u201320, 2016, Orl\u00e9ans, France, vol.\u00a047 of LIPIcs, pp. 31:1\u201331:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.31","DOI":"10.4230\/LIPIcs.STACS.2016.31"},{"issue":"3","key":"965_CR27","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(85)90001-X","volume":"6","author":"M Farber","year":"1985","unstructured":"Farber, M., Mark Keil, J.: Domination in permutation graphs. J. Algorithms 6(3), 309\u2013321 (1985). https:\/\/doi.org\/10.1016\/0196-6774(85)90001-X","journal-title":"J. Algorithms"},{"issue":"1","key":"965_CR28","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.1145\/3155298","volume":"14","author":"FV Fomin","year":"2018","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Kernels for (connected) dominating set on graphs with excluded topological minors. ACM Trans. Algorithms 14(1), 6:1-6:31 (2018)","journal-title":"ACM Trans. Algorithms"},{"issue":"6","key":"965_CR29","doi-asserted-by":"publisher","first-page":"1397","DOI":"10.1137\/16M1080264","volume":"49","author":"FV Fomin","year":"2020","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. SIAM J. Comput. 49(6), 1397\u20131422 (2020). https:\/\/doi.org\/10.1137\/16M1080264","journal-title":"SIAM J. Comput."},{"key":"965_CR30","doi-asserted-by":"publisher","unstructured":"Fomin, F. V., Thilikos, D. M.: Fast parameterized algorithms for graphs on surfaces: linear kernel and exponential speed-up. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D., (eds), Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12\u201316, 2004. Proceedings, vol. 3142 of Lecture Notes in Computer Science, pp. 581\u2013592. Springer (2004). https:\/\/doi.org\/10.1007\/978-3-540-27836-8_50","DOI":"10.1007\/978-3-540-27836-8_50"},{"issue":"2","key":"965_CR31","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0097539702419649","volume":"36","author":"FV Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: branch-width and exponential speed-up. SIAM J. Comput. 36(2), 281\u2013309 (2006). https:\/\/doi.org\/10.1137\/S0097539702419649","journal-title":"SIAM J. Comput."},{"key":"965_CR32","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). https:\/\/doi.org\/10.1016\/j.jcss.2016.09.002","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"965_CR33","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified np-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976). https:\/\/doi.org\/10.1016\/0304-3975(76)90059-1","journal-title":"Theor. Comput. Sci."},{"key":"965_CR34","doi-asserted-by":"crossref","unstructured":"Golovach, P. A., Villanger, Y.: Parameterized complexity for domination problems on degenerate graphs. In: Broersma, H., Erlebach, T., Friedetzky, , T., Paulusma, D., (eds), Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30\u2013July 2, 2008. Revised Papers","DOI":"10.1007\/978-3-540-92248-3_18"},{"issue":"3","key":"965_CR35","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/3051095","volume":"64","author":"M Grohe","year":"2017","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. J. ACM 64(3), 17:1-17:32 (2017). https:\/\/doi.org\/10.1145\/3051095","journal-title":"J. ACM"},{"issue":"4","key":"965_CR36","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF02579139","volume":"4","author":"M Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Corrigendum to our paper \u201cthe ellipsoid method and its consequences in combinatorial optimization\u2019\u2019. Combinatorica 4(4), 291\u2013295 (1984). https:\/\/doi.org\/10.1007\/BF02579139","journal-title":"Combinatorica"},{"key":"965_CR37","doi-asserted-by":"publisher","unstructured":"Gutner, S.: Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor. In: Chen, J., Fomin, F. V., (eds) Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers, vol. 5917 of Lecture Notes in Computer Science, pp. 246\u2013257. Springer (2009). https:\/\/doi.org\/10.1007\/978-3-642-11269-0_20","DOI":"10.1007\/978-3-642-11269-0_20"},{"issue":"2","key":"965_CR38","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.dam.2004.01.011","volume":"145","author":"M Habib","year":"2005","unstructured":"Habib, M., Paul, C.: A simple linear time algorithm for cograph recognition. Discret. Appl. Math. 145(2), 183\u2013197 (2005). https:\/\/doi.org\/10.1016\/j.dam.2004.01.011","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"965_CR39","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/3301445","volume":"15","author":"D Hermelin","year":"2019","unstructured":"Hermelin, D., Mnich, M., van Leeuwen, E.J., Woeginger, G.J.: Domination when the stars are out. ACM Trans. Algorithms 15(2), 25:1-25:90 (2019). https:\/\/doi.org\/10.1145\/3301445","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"965_CR40","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/2797140","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:1-21:41 (2016). https:\/\/doi.org\/10.1145\/2797140","journal-title":"ACM Trans. Algorithms"},{"key":"965_CR41","doi-asserted-by":"publisher","unstructured":"Koana, T., Komusiewicz, C., Sommer, F.: Exploiting c-closure in kernelization algorithms for graph problems. In: Grandoni, F., Herman, G., Sanders, P., (eds.) 28th Annual European Symposium on Algorithms, ESA 2020, September 7\u20139, 2020, Pisa, Italy (Virtual Conference), vol. 173 of LIPIcs, pp. 65:1\u201365:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.65","DOI":"10.4230\/LIPIcs.ESA.2020.65"},{"issue":"2","key":"965_CR42","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982). https:\/\/doi.org\/10.1137\/0211025","journal-title":"SIAM J. Comput."},{"issue":"1","key":"965_CR43","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.jcta.2004.04.002","volume":"107","author":"A Marcus","year":"2004","unstructured":"Marcus, A., Tardos, G.: Excluded permutation matrices and the Stanley\u2013Wilf conjecture. Comb. Theory Ser. A 107(1), 153\u2013160 (2004). https:\/\/doi.org\/10.1016\/j.jcta.2004.04.002","journal-title":"Comb. Theory Ser. A"},{"key":"965_CR44","doi-asserted-by":"publisher","unstructured":"Nesetril, J., Ossona de Mendez, P.: Sparsity - Graphs, Structures, and Algorithms, vol. 28 of Algorithms and combinatorics. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4","DOI":"10.1007\/978-3-642-27875-4"},{"issue":"1","key":"965_CR45","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/2390176.2390187","volume":"9","author":"G Philip","year":"2012","unstructured":"Philip, G., Raman, V., Sikdar, S.: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms 9(1), 11:1-11:23 (2012). https:\/\/doi.org\/10.1145\/2390176.2390187","journal-title":"ACM Trans. Algorithms"},{"key":"965_CR46","unstructured":"Przybyszewski, W., Toru\u0144czyk, S.: Personal communication (2021)"},{"key":"965_CR47","doi-asserted-by":"publisher","unstructured":"Raman, V., Saurabh, S.: Short cycles make W -hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles. Algorithmica 52(2), 203\u2013225 (2008). https:\/\/doi.org\/10.1007\/s00453-007-9148-9","DOI":"10.1007\/s00453-007-9148-9"},{"key":"965_CR48","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.tcs.2018.10.030","volume":"770","author":"JA Telle","year":"2019","unstructured":"Telle, J.A., Villanger, Y.: FPT algorithms for domination in sparse graphs and beyond. Theor. Comput. Sci. 770, 62\u201368 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2018.10.030","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00965-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00965-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00965-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,25]],"date-time":"2022-10-25T12:23:28Z","timestamp":1666700608000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00965-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,19]]},"references-count":48,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["965"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00965-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,19]]},"assertion":[{"value":"29 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}