{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:48:07Z","timestamp":1770994087893,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642404498","type":"print"},{"value":"9783642404504","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_45","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T03:22:47Z","timestamp":1376623367000},"page":"529-540","source":"Crossref","is-referenced-by-count":10,"title":["Kernelization Using Structural Parameters on Sparse Graph Classes"],"prefix":"10.1007","author":[{"given":"Jakub","family":"Gajarsk\u00fd","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr","family":"Hlin\u011bn\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Obdr\u017e\u00e1lek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Ordyniak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felix","family":"Reidl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fernando","family":"S\u00e1nchez Villaamil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Somnath","family":"Sikdar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"45_CR1","unstructured":"IPEC 2011. LNCS, vol.\u00a07112. Springer (2011)"},{"key":"45_CR2","first-page":"363","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for Dominating Set. J.\u00a0ACM\u00a051, 363\u2013384 (2004)","journal-title":"J.\u00a0ACM"},{"issue":"8","key":"45_CR3","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. Journal of Computer and System Sciences\u00a075(8), 423\u2013434 (2009)","journal-title":"Journal of Computer and System Sciences"},{"key":"45_CR4","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization. In: Proc. of 50th FOCS, pp. 629\u2013638. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.46"},{"key":"45_CR5","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernel bounds for path and cycle problems. In: IPEC 2011 [1], pp. 145\u2013158","DOI":"10.1007\/978-3-642-28050-4_12"},{"key":"45_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/3-540-54233-7_162","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"1991","unstructured":"Bodlaender, H.L., Kloks, T.: Better algorithms for the pathwidth and treewidth of graphs. In: Leach Albert, J., Monien, B., Rodr\u00edguez-Artalejo, M. (eds.) ICALP 1991. LNCS, vol.\u00a0510, pp. 544\u2013555. Springer, Heidelberg (1991)"},{"key":"45_CR7","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. Inform. and Comput.\u00a085, 12\u201375 (1990)","journal-title":"Inform. and Comput."},{"key":"45_CR8","doi-asserted-by":"crossref","unstructured":"Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: On cutwidth parameterized by vertex cover. In: IPEC 2011 [1], pp. 246\u2013258","DOI":"10.1007\/978-3-642-28050-4_20"},{"key":"45_CR9","unstructured":"de Fluiter, B.: Algorithms for Graphs of Small Treewidth. PhD thesis, Utrecht University (1997)"},{"key":"45_CR10","doi-asserted-by":"crossref","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 251\u2013260. ACM (2010)","DOI":"10.1145\/1806689.1806725"},{"key":"45_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"},{"key":"45_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/978-3-642-32589-2_32","volume-title":"Mathematical Foundations of Computer Science 2012","author":"M. Doucha","year":"2012","unstructured":"Doucha, M., Kratochv\u00edl, J.: Cluster vertex deletion: a parameterization between vertex cover and clique-width. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 348\u2013359. Springer, Heidelberg (2012)"},{"key":"45_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-642-11409-0_2","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Z. Dvo\u0159\u00e1k","year":"2010","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1l, D.: Algorithms for classes of graphs with bounded expansion. In: Paul, C., Habib, M. (eds.) WG 2009. LNCS, vol.\u00a05911, pp. 17\u201332. Springer, Heidelberg (2010)"},{"key":"45_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-540-92182-0_28","volume-title":"Algorithms and Computation","author":"M.R. Fellows","year":"2008","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 294\u2013305. Springer, Heidelberg (2008)"},{"key":"45_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-3-642-02017-9_25","volume-title":"Theory and Applications of Models of Computation","author":"J. Fiala","year":"2009","unstructured":"Fiala, J., Golovach, P.A., Kratochv\u00edl, J.: Parameterized complexity of coloring problems: Treewidth versus vertex cover. In: Chen, J., Cooper, S.B. (eds.) TAMC 2009. LNCS, vol.\u00a05532, pp. 221\u2013230. Springer, Heidelberg (2009)"},{"key":"45_CR16","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Philip, G., Saurabh, S.: Hitting forbidden minors: Approximation and kernelization. In: Proc. of 28th STACS. LIPIcs, vol.\u00a09, pp. 189\u2013200. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2011)"},{"key":"45_CR17","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar \n                  \n                    \n                  \n                  $\\mathcal{F}$\n                -Deletion: Approximation and Optimal FPT Algorithms. In: FOCS 2012, pp. 470\u2013479. IEEE Computer Society (2012)","DOI":"10.1109\/FOCS.2012.62"},{"key":"45_CR18","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proc. of 21st SODA, pp. 503\u2013510. SIAM (2010)","DOI":"10.1137\/1.9781611973075.43"},{"key":"45_CR19","doi-asserted-by":"crossref","unstructured":"Ganian, R.: Twin-cover: beyond vertex cover in parameterized algorithmics. In: IPEC 2011 [1], pp. 259\u2013271","DOI":"10.1007\/978-3-642-28050-4_21"},{"key":"45_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-540-73420-8_34","volume-title":"Automata, Languages and Programming","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Linear problem kernels for NP-hard problems on planar graphs. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 375\u2013386. Springer, Heidelberg (2007)"},{"key":"45_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/978-3-642-39206-1_52","volume-title":"Automata, Languages, and Programming","author":"E.J. Kim","year":"2013","unstructured":"Kim, E.J., Langer, A., Paul, C., Reidl, F., Rossmanith, P., Sau, I., Sikdar, S.: Linear kernels and single-exponential algorithms via protrusion decomposition. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 613\u2013624. Springer, Heidelberg (2013)"},{"key":"45_CR22","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Linear time low tree-width partitions and algorithmic consequences. In: STOC 2006, pp. 391\u2013400. ACM (2006)","DOI":"10.1145\/1132516.1132575"},{"issue":"3","key":"45_CR23","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1016\/j.ejc.2006.07.013","volume":"29","author":"J. Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Grad and classes with bounded expansion I. Decompositions. European J. Combin.\u00a029(3), 760\u2013776 (2008)","journal-title":"European J. Combin."},{"issue":"3","key":"45_CR24","doi-asserted-by":"publisher","first-page":"868","DOI":"10.2178\/jsl\/1278682204","volume":"75","author":"J. Ne\u0161et\u0159il","year":"2010","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: First order properties on nowhere dense structures. The Journal of Symbolic Logic\u00a075(3), 868\u2013887 (2010)","journal-title":"The Journal of Symbolic Logic"},{"issue":"4","key":"45_CR25","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1016\/j.ejc.2011.01.006","volume":"32","author":"J. Ne\u0161et\u0159il","year":"2011","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: On nowhere dense graphs. European J. Combin.\u00a032(4), 600\u2013617 (2011)","journal-title":"European J. Combin."},{"key":"45_CR26","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics, vol.\u00a028. Springer (2012)","DOI":"10.1007\/978-3-642-27875-4"},{"issue":"3","key":"45_CR27","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1016\/j.ejc.2011.09.008","volume":"33","author":"J. Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P., Wood, D.R.: Characterisations and examples of graph classes with bounded expansion. Eur. J. Comb.\u00a033(3), 350\u2013373 (2012)","journal-title":"Eur. J. Comb."},{"key":"45_CR28","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00373-007-0738-8","volume":"23","author":"D. Wood","year":"2007","unstructured":"Wood, D.: On the maximum number of cliques in a graph. Graphs and Combinatorics\u00a023, 337\u2013352 (2007)","journal-title":"Graphs and Combinatorics"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T16:51:48Z","timestamp":1558025508000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}