{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:38Z","timestamp":1759638638409,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":78,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642112683"},{"type":"electronic","value":"9783642112690"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-11269-0_2","type":"book-chapter","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T08:36:15Z","timestamp":1259656575000},"page":"17-37","source":"Crossref","is-referenced-by-count":59,"title":["Kernelization: New Upper and Lower Bound Techniques"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0168-0072(94)00034-Z","volume":"73","author":"K.A. Abrahamson","year":"1995","unstructured":"Abrahamson, K.A., Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. Annals of Pure and Applied Logic\u00a073, 235\u2013276 (1995)","journal-title":"Annals of Pure and Applied Logic"},{"doi-asserted-by":"crossref","unstructured":"Abrahamson, K.R., Fellows, M.R.: Finite automata, bounded treewidth and well-quasiordering. In: Robertson, N., Seymour, P. (eds.) Proceedings of the AMS Summer Workshop on Graph Minors, Graph Structure Theory. Contemporary Mathematics, vol.\u00a0147, pp. 539\u2013564. American Mathematical Society (1993)","key":"2_CR2","DOI":"10.1090\/conm\/147\/01199"},{"unstructured":"Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., Symons, C.T.: Kernelization algorithms for the vertex cover problem: Theory and experiments. In: Proceedings of the 6th Workshop on Algorithm Engineering and Experimentation and the 1st Workshop on Analytic Algorithmics and Combinatorics, ALENEX\/ANALCO 2004, pp. 62\u201369. ACM-SIAM (2004)","key":"2_CR3"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s00224-007-1328-0","volume":"41","author":"F.N. Abu-Khzam","year":"2007","unstructured":"Abu-Khzam, F.N., Fellows, M.R., Langston, M.A., Suters, W.H.: Crown structures for vertex cover kernelization. Theory of Computing Systems\u00a041, 411\u2013430 (2007)","journal-title":"Theory of Computing Systems"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s10479-006-0045-4","volume":"146","author":"J. Alber","year":"2006","unstructured":"Alber, J., Betzler, N., Niedermeier, R.: Experiments in data reduction for optimal domination in networks. Annals of Operations Research\u00a0146, 105\u2013117 (2006)","journal-title":"Annals of Operations Research"},{"key":"2_CR6","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 sets. J. ACM\u00a051, 363\u2013384 (2004)","journal-title":"J. ACM"},{"key":"2_CR7","first-page":"429","volume":"21","author":"K. Appel","year":"1977","unstructured":"Appel, K., Haken, W.: Every planar map is 4-colorable. Illinois J. Math.\u00a021, 429\u2013567 (1977)","journal-title":"Illinois J. Math."},{"key":"2_CR8","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\u00a040, 1134\u20131164 (1993)","journal-title":"J. ACM"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM\u00a041, 153\u2013180 (1994)","journal-title":"J. ACM"},{"unstructured":"Bessy, S., Fomin, F.V., Gaspers, S., Paul, C., Perez, A., Saurabh, S., Thomass\u00e9, S.: Kernels for feedback arc set in tournaments. The Computing Research Repository, abs\/0907.2165. To appear in proceedings FSTTCS 2009 (2009)","key":"2_CR10"},{"key":"2_CR11","doi-asserted-by":"publisher","first-page":"4554","DOI":"10.1016\/j.tcs.2009.08.033","volume":"410","author":"N. Betzler","year":"2009","unstructured":"Betzler, N., Fellows, M.R., Guo, J., Niedermeier, R., Rosamond, F.A.: Fixed-parameter algorithms for Kemeny rankings. Theor. Comp. Sc.\u00a0410, 4554\u20134570 (2009)","journal-title":"Theor. Comp. Sc."},{"key":"2_CR12","first-page":"481","volume-title":"Handbook of Operations Research and Management Science: Network Models","author":"D. Bienstock","year":"1995","unstructured":"Bienstock, D., Langston, M.A.: Algorithmic implications of the graph minor theorem. In: Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L. (eds.) Handbook of Operations Research and Management Science: Network Models, pp. 481\u2013502. North-Holland, Amsterdam (1995)"},{"doi-asserted-by":"crossref","unstructured":"B\u00f6cker, S., Briesemeister, S., Klau, G.W.: Exact algorithms for cluster editing: Evaluation and experiments. To appear in Algorithmica (2009) doi 10.1007\/s00453-009-9339-7","key":"2_CR13","DOI":"10.1007\/s00453-009-9339-7"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comp. Sc.\u00a0209, 1\u201345 (1998)","journal-title":"Theor. Comp. Sc."},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/978-3-540-70575-8_46","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels (Extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 563\u2013574. Springer, Heidelberg (2008)"},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-540-73545-8_11","volume-title":"Computing and Combinatorics","author":"H.L. Bodlaender","year":"2007","unstructured":"Bodlaender, H.L., Fellows, M.R., Langston, M., Ragan, M., Rosamond, F., Weyer, M.: Quadratic kernelization for convex recoloring of trees. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 86\u201396. Springer, Heidelberg (2007)"},{"doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M. (Meta) kernelization. To appear in Proceedings FOCS 2009 (2009)","key":"2_CR17","DOI":"10.1109\/FOCS.2009.46"},{"doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Lokshtanov, D., Penninkx, E.: Planar capacitated dominating set is W[1]-hard. In: Proceedings IWPEC 2009 (2009)","key":"2_CR18","DOI":"10.1007\/978-3-642-11269-0_4"},{"key":"2_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/978-3-540-79723-4_16","volume-title":"Parameterized and Exact Computation","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Penninkx, E.: A linear kernel for planar feedback vertex set. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol.\u00a05018, pp. 160\u2013171. Springer, Heidelberg (2008)"},{"key":"2_CR20","series-title":"Lecture Notes in Computer Science","first-page":"294","volume-title":"Algorithms and Computation","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Penninkx, E., Tan, R.B.: A linear kernel for the k-disjoint cycle problem on planar graphs. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 294\u2013305. Springer, Heidelberg (2008)"},{"key":"2_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/978-3-642-04128-0_57","volume-title":"ESA 2009","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 635\u2013646. Springer, Heidelberg (2009)"},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1006\/inco.2000.2958","volume":"167","author":"H.L. Bodlaender","year":"2001","unstructured":"Bodlaender, H.L., van Antwerpen-de Fluiter, B.: Reduction algorithms for graphs of small treewidth. Information and Computation\u00a0167, 86\u2013119 (2001)","journal-title":"Information and Computation"},{"doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., van Dijk, T.C.: A cubic kernel for feedback vertex set and loop cutset. To appear in Theory of Computing Systems (2009) doi: 10.1007\/s00224-009-9234-2","key":"2_CR23","DOI":"10.1007\/s00224-009-9234-2"},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R.B. Borie","year":"1992","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica\u00a07, 555\u2013581 (1992)","journal-title":"Algorithmica"},{"unstructured":"Bousquet, N., Daligault, J., Thomass\u00e9, S., Yeo, A.: A polynomial kernel for multicut in trees. In: Albers, S., Marion, J.-Y. (eds.) Proceedings 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, Schloss Dagstuhl, Germany. Dagstuhl Seminar Proceedings, vol.\u00a009001, pp. 183\u2013194. Leibniz-Zentrum f\u00fcr Informatik (2009)","key":"2_CR25"},{"key":"2_CR26","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"J.F. Buss","year":"1993","unstructured":"Buss, J.F., Goldsmith, J.: Nondeterminism within P. SIAM J. Comput.\u00a022, 560\u2013572 (1993)","journal-title":"SIAM J. Comput."},{"key":"2_CR27","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1006\/jcss.1997.1490","volume":"54","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J.: On fixed-parameter tractability and approximability of NP optimization problems. Journal of Computer and System Sciences\u00a054, 465\u2013474 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0168-0072(95)00020-8","volume":"84","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: Advice classes of parameterized tractability. Annals of Pure and Applied Logic\u00a084, 119\u2013138 (1997)","journal-title":"Annals of Pure and Applied Logic"},{"key":"2_CR29","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L. Cai","year":"2003","unstructured":"Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. Journal of Computer and System Sciences\u00a067, 789\u2013807 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","volume":"201","author":"J. Chen","year":"2005","unstructured":"Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D.W., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Information and Computation\u00a0201, 216\u2013231 (2005)","journal-title":"Information and Computation"},{"key":"2_CR31","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.\u00a037, 1077\u20131106 (2007)","journal-title":"SIAM J. Comput."},{"key":"2_CR32","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10878-006-7137-6","volume":"11","author":"J. Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: On the computational hardness based on linear FPT-reductions. Journal of Combinatorial Optimization\u00a011, 231\u2013247 (2006)","journal-title":"Journal of Combinatorial Optimization"},{"key":"2_CR33","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. Journal of Computer and System Sciences\u00a072, 1346\u20131367 (2006)","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"Chen, J., Lu, S., Sze, S.-H., Zhang, F.: Improved algorithms for path, matching, and packing problems. In: Bansal, N., Pruhs, K., Stein, C. (eds.) Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pp. 298\u2013307 (2007)","key":"2_CR34"},{"key":"2_CR35","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. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"doi-asserted-by":"crossref","unstructured":"Daligault, J., Thomass\u00e9, S.: On finding directed trees with many leaves. In: Proceedings IWPEC 2009 (2009)","key":"2_CR36","DOI":"10.1007\/978-3-642-11269-0_7"},{"unstructured":"de Fluiter, B.: Algorithms for Graphs of Small Treewidth. PhD thesis, Utrecht University (1997)","key":"2_CR37"},{"key":"2_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/11611257_21","volume-title":"SOFSEM 2006: Theory and Practice of Computer Science","author":"F. Dehne","year":"2006","unstructured":"Dehne, F., Fellows, M., Fernau, H., Prieto, E., Rosamond, F.: Nonblocker: Parameterized algorithms for minimum dominating set. In: Wiedermann, J., Tel, G., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2006. LNCS, vol.\u00a03831, pp. 237\u2013245. Springer, Heidelberg (2006)"},{"doi-asserted-by":"crossref","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: To appear in: Electronic Colloquium on Computational Complexity (ECCC), vol.\u00a016 (2009)","key":"2_CR39","DOI":"10.1145\/1806689.1806725"},{"key":"2_CR40","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1093\/comjnl\/bxm033","volume":"51","author":"E.D. Demaine","year":"2008","unstructured":"Demaine, E.D., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. The Computer Journal\u00a051, 292\u2013302 (2008)","journal-title":"The Computer Journal"},{"key":"2_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"ICALP 2009, Part I","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 378\u2013389. Springer, Heidelberg (2009)"},{"key":"2_CR42","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: Basic results. SIAM J. Comput.\u00a024, 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"key":"2_CR43","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for W[1]. Theor. Comp. Sc.\u00a0141, 109\u2013131 (1995)","journal-title":"Theor. Comp. Sc."},{"key":"2_CR44","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R., Stege, U.: Parameterized complexity: A framework for systematically confronting computational intractability. In: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 49\u201399. American Mathematical Society (1997)","key":"2_CR45","DOI":"10.1090\/dimacs\/049\/04"},{"key":"2_CR46","series-title":"Text in Algorithms","first-page":"1","volume-title":"Proceedings of the 1st Workshop on Algorithms and Complexity in Durham, ACiD 2005","author":"V. Estivill-Castro","year":"2005","unstructured":"Estivill-Castro, V., Fellows, M.R., Langston, M.A., Rosamond, F.A.: Fpt is P-time extremal structure I. In: Broersma, H., Johnson, M., Szeider, S. (eds.) Proceedings of the 1st Workshop on Algorithms and Complexity in Durham, ACiD 2005. Text in Algorithms, vol.\u00a04, pp. 1\u201341. King\u2019s College, London (2005)"},{"unstructured":"Fellows, M.R.: Personal communication","key":"2_CR47"},{"doi-asserted-by":"crossref","unstructured":"Fellows, M.R., Langston, M.A.: An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, FOCS 1989, pp. 520\u2013525 (1989)","key":"2_CR48","DOI":"10.1109\/SFCS.1989.63528"},{"key":"2_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/11847250_13","volume-title":"Parameterized and Exact Computation","author":"H. Fernau","year":"2006","unstructured":"Fernau, H.: Edge dominating set: Efficient enumeration-based exact algorithms. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 140\u2013151. Springer, Heidelberg (2006)"},{"unstructured":"Fernau, H., Fomin, F.V., Lokshtanov, D., Raible, D., Saurabh, S., Villanger, Y.: Kernel(s) for problems with no kernel: On out-trees with many leaves (extended abstract). In: Albers, S., Marion, J.-Y. (eds.) Proceedings 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, Schloss Dagstuhl, Germany. Dagstuhl Seminar Proceedings, vol.\u00a009001, pp. 421\u2013432. Leibniz-Zentrum f\u00fcr Informatik (2009)","key":"2_CR50"},{"key":"2_CR51","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1007\/978-3-540-28629-5_37","volume-title":"Mathematical Foundations of Computer Science 2004","author":"H. Fernau","year":"2004","unstructured":"Fernau, H., Juedes, D.W.: A geometric approach to parameterized algorithms for domination problems on planar graphs. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol.\u00a03153, pp. 488\u2013499. Springer, Heidelberg (2004)"},{"key":"2_CR52","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Algorithmic lower bounds for problems parameterized by clique-width. To appear in Proceedings SODA 2010 (2009)","key":"2_CR53","DOI":"10.1137\/1.9781611973075.42"},{"doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. To appear in Proceedings SODA 2010 (2009)","key":"2_CR54","DOI":"10.1137\/1.9781611973075.43"},{"key":"2_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1007\/978-3-540-27836-8_50","volume-title":"Automata, Languages and Programming","author":"F.V. Fomin","year":"2004","unstructured":"Fomin, F.V., Thilikos, D.M.: Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speedup. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 581\u2013592. Springer, Heidelberg (2004)"},{"key":"2_CR56","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1145\/1374376.1374398","volume-title":"Proceedings of the 40th Annual Symposium on Theory of Computing, STOC 2008","author":"L. Fortnow","year":"2008","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: Proceedings of the 40th Annual Symposium on Theory of Computing, STOC 2008, pp. 133\u2013142. ACM Press, New York (2008)"},{"doi-asserted-by":"crossref","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Data reduction and exact algorithms for clique cover. ACM Journal of Experimental Algorithms13(2.2) (2008)","key":"2_CR57","DOI":"10.1145\/1412228.1412236"},{"key":"2_CR58","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1016\/j.tcs.2008.10.021","volume":"410","author":"J. Guo","year":"2009","unstructured":"Guo, J.: A more effective linear kernelization for cluster editing. Theor. Comp. Sc.\u00a0410, 718\u2013726 (2009)","journal-title":"Theor. Comp. Sc."},{"key":"2_CR59","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News\u00a038, 31\u201345 (2007)","journal-title":"ACM SIGACT News"},{"key":"2_CR60","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":"2_CR61","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/11847250_19","volume-title":"Parameterized and Exact Computation","author":"J. Guo","year":"2006","unstructured":"Guo, J., Niedermeier, R., Wernicke, S.: Fixed-parameter tractability results for full-degree spanning tree and its dual. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 203\u2013214. Springer, Heidelberg (2006)"},{"key":"2_CR62","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s00224-007-1309-3","volume":"41","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of vertex cover variants. Theory of Computing Systems\u00a041, 501\u2013520 (2007)","journal-title":"Theory of Computing Systems"},{"key":"2_CR63","doi-asserted-by":"publisher","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. Comp. Sc.\u00a0410, 4571\u20134579 (2009)","journal-title":"Theor. Comp. Sc."},{"key":"2_CR64","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/978-3-642-11269-0_20","volume-title":"IWPEC 2009","author":"S. Gutner","year":"2009","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.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 246\u2013257. Springer, Heidelberg (2009)"},{"unstructured":"Jansen, B.: Fixed parameter complexity of the weighted max leaf problem. Master\u2019s thesis, Department of Computer Science, Utrecht University (2009)","key":"2_CR65"},{"key":"2_CR66","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/11549345_49","volume-title":"Mathematical Foundations of Computer Science 2005","author":"J. Kneis","year":"2005","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: On the parameterized complexity of exact satisfiability problems. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 568\u2013579. Springer, Heidelberg (2005)"},{"unstructured":"Kratsch, S.: Polynomial kernelizations for MIN F$^+\\Pi_1$ and MAX NP. In: Albers, S., Marion, J.-Y. (eds.) Proceedings 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, Schloss Dagstuhl, Germany. Dagstuhl Seminar Proceedings, vol.\u00a009001, pp. 601\u2013612. Leibniz-Zentrum f\u00fcr Informatik (2009)","key":"2_CR67"},{"doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Two edge modification problems without polynomial kernels. In: Proceedings IWPEC 2009 (2009)","key":"2_CR68","DOI":"10.1007\/978-3-642-11269-0_22"},{"key":"2_CR69","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/978-3-642-02017-9_31","volume-title":"TAMC 2009","author":"D. Lokshtanov","year":"2009","unstructured":"Lokshtanov, D., Mnich, M., Saurabh, S.: Linear kernel for planar connected dominating set. In: Chen, J., Cooper, S.B. (eds.) TAMC 2009. LNCS, vol.\u00a05532, pp. 281\u2013290. Springer, Heidelberg (2009)"},{"key":"2_CR70","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/978-3-540-95891-8_37","volume-title":"SOFSEM 2009: Theory and Practice of Computer Science","author":"H. Moser","year":"2009","unstructured":"Moser, H.: A problem kernelization for graph packing. In: Nielsen, M., Kucera, A., Miltersen, P.B., Palamidessi, C., Tuma, P., Valencia, F.D. (eds.) SOFSEM 2009. LNCS, vol.\u00a05404, pp. 401\u2013412. Springer, Heidelberg (2009)"},{"key":"2_CR71","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1016\/j.dam.2008.07.011","volume":"157","author":"H. Moser","year":"2009","unstructured":"Moser, H., Sikdar, S.: The parameterized complexity of the induced matching problem. Disc. Appl. Math.\u00a0157, 715\u2013727 (2009)","journal-title":"Disc. Appl. Math."},{"key":"2_CR72","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packing: Structural properties and algorithms. Mathematical Programming\u00a08, 232\u2013248 (1975)","journal-title":"Mathematical Programming"},{"key":"2_CR73","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2006)"},{"key":"2_CR74","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"694","DOI":"10.1007\/978-3-642-04128-0_62","volume-title":"ESA 2009","author":"G. Philip","year":"2009","unstructured":"Philip, G., Raman, V., Sikdar, S.: Solving dominating set in larger classes of graphs: FPT algorithms and polynomial kernels. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 694\u2013705. Springer, Heidelberg (2009)"},{"key":"2_CR75","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Comb. Theory Series B\u00a036, 49\u201364 (1984)","journal-title":"J. Comb. Theory Series B"},{"key":"2_CR76","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 Series B\u00a063, 65\u2013110 (1995)","journal-title":"J. Comb. Theory Series B"},{"key":"2_CR77","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Comb. Theory Series B\u00a092, 325\u2013357 (2004)","journal-title":"J. Comb. Theory Series B"},{"doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S.: A quadratic kernel for feedback vertex set. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pp. 115\u2013119 (2009)","key":"2_CR78","DOI":"10.1137\/1.9781611973068.13"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11269-0_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T21:04:39Z","timestamp":1674853479000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-11269-0_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642112683","9783642112690"],"references-count":78,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11269-0_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}