{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:30Z","timestamp":1759637730545},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319944173"},{"type":"electronic","value":"9783319944180"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-94418-0_17","type":"book-chapter","created":{"date-parts":[[2018,7,4]],"date-time":"2018-07-04T16:38:26Z","timestamp":1530722306000},"page":"161-171","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Diminishable Parameterized Problems and Strict Polynomial Kernelization"],"prefix":"10.1007","author":[{"given":"Henning","family":"Fernau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Till","family":"Fluschnik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Hermelin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Krebs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hendrik","family":"Molter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,7,3]]},"reference":[{"key":"17_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/11847250_24","volume-title":"Parameterized and Exact Computation","author":"FN Abu-Khzam","year":"2006","unstructured":"Abu-Khzam, F.N., Fernau, H.: Kernels: annotated, proper and induced. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 264\u2013275. Springer, Heidelberg (2006). \nhttps:\/\/doi.org\/10.1007\/11847250_24"},{"issue":"4","key":"17_CR2","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"issue":"4","key":"17_CR3","doi-asserted-by":"publisher","first-page":"774","DOI":"10.1016\/j.jcss.2010.07.005","volume":"77","author":"N Betzler","year":"2011","unstructured":"Betzler, N., Guo, J., Komusiewicz, C., Niedermeier, R.: Average parameterization and partial kernelization for computing medians. J. Comput. Syst. Sci. 77(4), 774\u2013789 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"17_CR4","doi-asserted-by":"publisher","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"},{"issue":"8","key":"17_CR5","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)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"17_CR6","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. Ann. Pure Appl. Logic 84(1), 119\u2013138 (1997)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"4","key":"17_CR7","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)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"17_CR8","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1007\/s00224-010-9270-y","volume":"48","author":"Y Chen","year":"2011","unstructured":"Chen, Y., Flum, J., M\u00fcller, M.: Lower bounds for kernelizations and other preprocessing procedures. Theory Comput. Syst. 48(4), 803\u2013839 (2011)","journal-title":"Theory Comput. Syst."},{"key":"17_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory, 4th edn. Springer, Heidelberg (2010). \nhttps:\/\/doi.org\/10.1007\/978-3-662-53622-3","edition":"4"},{"key":"17_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Heidelberg (2013). \nhttps:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"17_CR11","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.jcss.2017.11.001","volume":"93","author":"MR Fellows","year":"2018","unstructured":"Fellows, M.R., Kulik, A., Rosamond, F.A., Shachnai, H.: Parameterized approximation via fidelity preserving transformations. J. Comput. Syst. Sci. 93, 30\u201340 (2018)","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR12","unstructured":"Fernau, H., Fluschnik, T., Hermelin, D., Krebs, A., Molter, H., Niedermeier, R.: Diminishable parameterized problems and strict polynomial kernelization. CoRR abs\/1611.03739 (2018). \nhttp:\/\/arxiv.org\/abs\/1611.03739"},{"key":"17_CR13","unstructured":"Fluschnik, T., Mertzios, G.B., Nichterlein, A.: Kernelization lower bounds for finding constant size subgraphs. CoRR abs\/1710.07601 (2017). \nhttp:\/\/arxiv.org\/abs\/1710.07601"},{"issue":"1","key":"17_CR14","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"17_CR15","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 38(1), 31\u201345 (2007)","journal-title":"ACM SIGACT News"},{"issue":"2","key":"17_CR16","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"17_CR17","first-page":"191","volume":"28","author":"RM Karp","year":"1982","unstructured":"Karp, R.M., Lipton, R.: Turing machines that take advice. L\u2019Enseignement Math\u00e9matique 28(2), 191\u2013209 (1982)","journal-title":"L\u2019Enseignement Math\u00e9matique"},{"key":"17_CR18","unstructured":"Kratsch, S.: Recent developments in kernelization: a survey. In: Bulletin of the EATCS, no. 113 (2014)"},{"issue":"2","key":"17_CR19","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S0020-0190(02)00227-2","volume":"84","author":"G Lin","year":"2002","unstructured":"Lin, G., Xue, G.: On the terminal Steiner tree problem. Inf. Process. Lett. 84(2), 103\u2013107 (2002)","journal-title":"Inf. Process. Lett."},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Panolan, F., Ramanujan, M.S., Saurabh, S.: Lossy kernelization. In: Proceedings of 49th STOC, pp. 224\u2013237. ACM (2017)","DOI":"10.1145\/3055399.3055456"},{"issue":"5","key":"17_CR21","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s11590-011-0311-5","volume":"6","author":"A Sch\u00e4fer","year":"2012","unstructured":"Sch\u00e4fer, A., Komusiewicz, C., Moser, H., Niedermeier, R.: Parameterized computational complexity of finding small-diameter subgraphs. Optim. Lett. 6(5), 883\u2013891 (2012)","journal-title":"Optim. Lett."}],"container-title":["Lecture Notes in Computer Science","Sailing Routes in the World of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-94418-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,7,4]],"date-time":"2018-07-04T16:48:06Z","timestamp":1530722886000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-94418-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319944173","9783319944180"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94418-0_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}