{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:59Z","timestamp":1759639079062,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662531730"},{"type":"electronic","value":"9783662531747"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53174-7_31","type":"book-chapter","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T14:50:06Z","timestamp":1470322206000},"page":"440-455","source":"Crossref","is-referenced-by-count":1,"title":["Polynomial Kernelization for Removing Induced Claws and Diamonds"],"prefix":"10.1007","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Wrochna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,5]]},"reference":[{"issue":"2","key":"31_CR1","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/S0021-9800(70)80019-9","volume":"9","author":"LW Beineke","year":"1970","unstructured":"Beineke, L.W.: Characterizations of derived graphs. J. Comb. Theor. 9(2), 129\u2013135 (1970)","journal-title":"J. Comb. Theor."},{"key":"31_CR2","unstructured":"Bliznets, I., Fomin, F.V., Pilipczuk, M., Pilipczuk, M.: A subexponential parameterized algorithm for Interval Completion (2014). CoRR, abs\/1402.3473"},{"key":"31_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/978-3-662-44777-2_15","volume-title":"Algorithms - ESA 2014","author":"I Bliznets","year":"2014","unstructured":"Bliznets, I., Fomin, F.V., Pilipczuk, M., Pilipczuk, M.: A subexponential parameterized algorithm for proper interval completion. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 173\u2013184. Springer, Heidelberg (2014)"},{"issue":"4","key":"31_CR4","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"key":"31_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/978-3-319-03898-8_9","volume-title":"Parameterized and Exact Computation","author":"L Cai","year":"2013","unstructured":"Cai, L., Cai, Y.: Incompressibility of H-free edge modification. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 84\u201396. Springer, Heidelberg (2013)"},{"key":"31_CR6","unstructured":"Cai, Y.: Polynomial kernelisation of $$H$$ -free edge modification problems. Master\u2019s thesis. The Chinese University of Hong Kong, Hong Kong (2012)"},{"issue":"5","key":"31_CR7","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1016\/j.jctb.2007.06.007","volume":"98","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky, M., Seymour, P.D.: Claw-free graphs. IV. Decomposition theorem. J. Comb. Theor. Ser. B 98(5), 839\u2013938 (2008)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"6","key":"31_CR8","doi-asserted-by":"crossref","first-page":"1373","DOI":"10.1016\/j.jctb.2008.03.002","volume":"98","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky, M., Seymour, P.D.: Claw-free graphs. V. Global structure. J. Comb. Theor. Ser. B 98(6), 1373\u20131410 (2008)","journal-title":"J. Comb. Theor. Ser. B"},{"key":"31_CR9","unstructured":"Cygan, M., Kowalik, L., Pilipczuk, M.: Open problems from workshop on kernels (2013). http:\/\/worker2013.mimuw.edu.pl\/slides\/worker-opl.pdf"},{"key":"31_CR10","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., van Leeuwen, E.J., Wrochna, M.: Polynomial kernelization for removing induced claws and diamonds (2015). CoRR, abs\/1503.00704"},{"key":"31_CR11","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"31_CR12","unstructured":"Drange, P.G., Fomin, F.V., Pilipczuk, M., Villanger, Y.: Exploring subexponential parameterized complexity of completion problems. In: STACS 2014, LIPIcs, vol. 25, pp. 288\u2013299. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2014)"},{"key":"31_CR13","doi-asserted-by":"crossref","unstructured":"Drange, P.G., Pilipczuk, M.: A polynomial kernel for Trivially Perfect Editing. CoRR, abs\/1412.7558 (2014)","DOI":"10.1007\/978-3-662-48350-3_36"},{"key":"31_CR14","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2006)"},{"issue":"4","key":"31_CR15","doi-asserted-by":"crossref","first-page":"1964","DOI":"10.1137\/12089051X","volume":"27","author":"FV Fomin","year":"2013","unstructured":"Fomin, F.V., Saurabh, S., Villanger, Y.: A polynomial kernel for proper interval vertex deletion. SIAM J. Discrete Math. 27(4), 1964\u20131976 (2013)","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"31_CR16","doi-asserted-by":"crossref","first-page":"2197","DOI":"10.1137\/11085390X","volume":"42","author":"FV Fomin","year":"2013","unstructured":"Fomin, F.V., Villanger, Y.: Subexponential parameterized algorithm for minimum fill-in. SIAM J. Comput. 42(6), 2197\u20132216 (2013)","journal-title":"SIAM J. Comput."},{"key":"31_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/978-3-642-31155-0_10","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"E Ghosh","year":"2012","unstructured":"Ghosh, E., Kolay, S., Kumar, M., Misra, P., Panolan, F., Rai, A., Ramanujan, M.S.: Faster parameterized algorithms for deletion to split graphs. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 107\u2013118. Springer, Heidelberg (2012)"},{"issue":"4","key":"31_CR18","doi-asserted-by":"crossref","first-page":"900","DOI":"10.1007\/s00453-012-9619-5","volume":"65","author":"S Guillemot","year":"2013","unstructured":"Guillemot, S., Havet, F., Paul, C., Perez, A.: On the (non-)existence of polynomial kernels for $$P_l$$ -free edge modification problems. Algorithmica 65(4), 900\u2013926 (2013)","journal-title":"Algorithmica"},{"issue":"3","key":"31_CR19","first-page":"513","volume":"70","author":"D Hermelin","year":"2014","unstructured":"Hermelin, D., Mnich, M., van Leeuwen, E.J.: Parameterized complexity of induced graph matching on claw-free graphs. Algorithmica 70(3), 513\u2013560 (2014)","journal-title":"Algorithmica"},{"issue":"4","key":"31_CR20","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"31_CR21","series-title":"LNCS","first-page":"106","volume-title":"WG 1994","author":"T Kloks","year":"1994","unstructured":"Kloks, T., Kratsch, D., M\u00fcller, H.: Dominoes. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol. 903, pp. 106\u2013120. Springer, Heidelberg (1994)"},{"issue":"15","key":"31_CR22","doi-asserted-by":"crossref","first-page":"2259","DOI":"10.1016\/j.dam.2012.05.019","volume":"160","author":"C Komusiewicz","year":"2012","unstructured":"Komusiewicz, C., Uhlmann, J.: Cluster editing with locally bounded modifications. Discrete Appl. Math. 160(15), 2259\u20132270 (2012)","journal-title":"Discrete Appl. Math."},{"key":"31_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1007\/978-3-642-11269-0_22","volume-title":"Parameterized and Exact Computation","author":"S Kratsch","year":"2009","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Two edge modification problems without polynomial kernels. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 264\u2013275. Springer, Heidelberg (2009)"},{"issue":"3","key":"31_CR24","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1137\/S089548019936521X","volume":"16","author":"Y Metelsky","year":"2003","unstructured":"Metelsky, Y., Tyshkevich, R.: Line graphs of Helly hypergraphs. SIAM J. Discrete Math. 16(3), 438\u2013448 (2003)","journal-title":"SIAM J. Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53174-7_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T12:53:28Z","timestamp":1749041608000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53174-7_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531730","9783662531747"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53174-7_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}