{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T12:48:21Z","timestamp":1772714901250,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,6,23]],"date-time":"2016-06-23T00:00:00Z","timestamp":1466640000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["DEC-2013\/11\/D\/ST6\/03073"],"award-info":[{"award-number":["DEC-2013\/11\/D\/ST6\/03073"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["DEC-2012\/05\/D\/ST6\/03214"],"award-info":[{"award-number":["DEC-2012\/05\/D\/ST6\/03214"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,5]]},"DOI":"10.1007\/s00224-016-9689-x","type":"journal-article","created":{"date-parts":[[2016,6,23]],"date-time":"2016-06-23T12:06:01Z","timestamp":1466683561000},"page":"615-636","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Polynomial Kernelization for Removing Induced Claws and Diamonds"],"prefix":"10.1007","volume":"60","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,6,23]]},"reference":[{"issue":"2","key":"9689_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. Theory 9(2), 129\u2013135 (1970)","journal-title":"J. Comb. Theory"},{"issue":"4","key":"9689_CR2","first-page":"1961","volume":"29","author":"I Bliznets","year":"2015","unstructured":"Bliznets, I., Fomin, F.V., Pilipczuk, M., Pilipczuk, M.: A subexponential parameterized algorithm for proper interval completion. SIAM J. Discrete Math. 29(4), 1961\u20131987 (2015). doi: 10.1137\/140988565","journal-title":"SIAM J. Discrete Math."},{"key":"9689_CR3","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1137\/1.9781611974331.ch78","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016","author":"I Bliznets","year":"2016","unstructured":"Bliznets, I., Fomin, F.V., Pilipczuk, M., Pilipczuk, M.: Subexponential parameterized algorithm for interval completion. In: Krauthgamer, R. (ed.) Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pp. 1116\u20131131. SIAM, Arlington (2016). doi: 10.1137\/1.9781611974331.ch78"},{"key":"9689_CR4","first-page":"51","volume":"32","author":"D Br\u00fcgmann","year":"2009","unstructured":"Br\u00fcgmann, D., Komusiewicz, C., Moser, H.: On generating triangle-free graphs. Electron. Notes Discrete Math. 32, 51\u201358 (2009). doi: 10.1016\/j.endm.2009.02.008","journal-title":"Electron Notes Discrete Math."},{"issue":"4","key":"9689_CR5","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."},{"issue":"3","key":"9689_CR6","first-page":"731","volume":"71","author":"L Cai","year":"2015","unstructured":"Cai, L., Cai, Y.: Incompressibility of H-free edge modification problems. Algorithmica 71(3), 731\u2013757 (2015). doi: 10.1007\/s00453-014-9937-x","journal-title":"Algorithmica"},{"key":"9689_CR7","volume-title":"Polynomial kernelisation of H-free edge modification problems","author":"Y Cai","year":"2012","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":"9689_CR8","first-page":"839","volume":"98","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky, M., Seymour, P.D.: Claw-free graphs. IV. Decomposition theorem. J. Comb. Theory, Ser. B 98(5), 839\u2013938 (2008). doi: 10.1016\/j.jctb.2007.06.007","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"6","key":"9689_CR9","first-page":"1373","volume":"98","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky, M., Seymour, P.D.: Claw-free graphs. V. Global structure. J. Comb. Theory, Ser. B 98(6), 1373\u20131410 (2008). doi: 10.1016\/j.jctb.2008.03.002","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9689_CR10","doi-asserted-by":"publisher","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015). doi: 10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"9689_CR11","unstructured":"Cygan, M., Kowalik, L., Pilipczuk, M.: Open Problems from Workshop on Kernels. Available at http:\/\/worker2013.mimuw.edu.pl\/slides\/worker-opl.pdf (2013)"},{"key":"9689_CR12","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer (1999). doi: 10.1007\/978-1-4612-0515-9","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"4","key":"9689_CR13","first-page":"14","volume":"7","author":"PG Drange","year":"2015","unstructured":"Drange, P.G., Fomin, F.V., Pilipczuk, M., Villanger, Y.: Exploring the subexponential complexity of completion problems. TOCT 7(4), 14 (2015). doi: 10.1145\/2799640","journal-title":"TOCT"},{"key":"9689_CR14","doi-asserted-by":"publisher","unstructured":"Drange, P.G., Pilipczuk, M.: A polynomial kernel for trivially perfect editing. In: Bansal, N., Finocchi, I. (eds.) Algorithms - ESA 2015, 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9294, pp. 424\u2013436. Springer (2015). doi: 10.1007\/978-3-662-48350-3_36","DOI":"10.1007\/978-3-662-48350-3_36"},{"key":"9689_CR15","doi-asserted-by":"publisher","unstructured":"Fellows, M., Heggernes, P., Rosamond, F.A., Sloper, C., Telle, J.A.: Finding k disjoint triangles in an arbitrary graph. In: Hromkovic, J., Nagl, M., Westfechtel, B. (eds.) Graph-Theoretic Concepts in Computer Science, 30th International Workshop, WG 2004. Revised Papers, Lecture Notes in Computer Science, vol. 3353, pp. 235\u2013244. Springer, Bad Honnef (2004). doi: 10.1007\/978-3-540-30559-0_20","DOI":"10.1007\/978-3-540-30559-0_20"},{"key":"9689_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin Heidelberg (2006). doi: 10.1007\/3-540-29953-X"},{"issue":"4","key":"9689_CR17","first-page":"1964","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). doi: 10.1137\/12089051X","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"9689_CR18","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":"9689_CR19","author":"E Ghosh","year":"2013","unstructured":"Ghosh, E., Kolay, S., Kumar, M., Misra, P., Panolan, F., Rai, A., Ramanujan, M.: Faster parameterized algorithms for deletion to split graphs. Algorithmica (2013). doi: 10.1007\/s00453-013-9837-5","journal-title":"Algorithmica"},{"issue":"4","key":"9689_CR20","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":"9689_CR21","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":"9689_CR22","first-page":"512","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). doi: 10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"key":"9689_CR23","doi-asserted-by":"publisher","unstructured":"Kloks, T., Kratsch, D., M\u00fcller, H.: Dominoes. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) Graph-Theoretic Concepts in Computer Science, 20th International Workshop, WG \u201994 Herrsching, Germany, June 16-18, 1994. Proceedings, Lecture Notes in Computer Science, vol. 903, pp. 106\u2013120. Springer (1994). doi: 10.1007\/3-540-59071-4_41","DOI":"10.1007\/3-540-59071-4_41"},{"issue":"15","key":"9689_CR24","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. Discret. Appl. Math. 160(15), 2259\u20132270 (2012)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"9689_CR25","first-page":"193","volume":"10","author":"S Kratsch","year":"2013","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Two edge modification problems without polynomial kernels. Discret. Optim. 10(3), 193\u2013199 (2013). doi: 10.1016\/j.disopt.2013.02.001","journal-title":"Discret. Optim."},{"issue":"3","key":"9689_CR26","first-page":"438","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). doi: 10.1137\/S089548019936521X","journal-title":"SIAM J. Discrete Math."},{"key":"9689_CR27","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/978-3-642-22993-0_45","volume-title":"Proceedings of Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011. Lecture Notes in Computer Science, vol. 6907","author":"C Paul","year":"2011","unstructured":"Paul, C., Perez, A., Thomass\u00e9, S.: Conflict packing yields linear vertex-kernels for k -fast, k -dense RTI and a related problem. In: Murlak, F., Sankowski, P. (eds.) Proceedings of Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011. Lecture Notes in Computer Science, vol. 6907, pp. 497\u2013507. Springer, Warsaw (2011). doi: 10.1007\/978-3-642-22993-0_45"},{"issue":"2","key":"9689_CR28","first-page":"297","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10(2), 297\u2013309 (1981). doi: 10.1137\/0210021","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9689-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9689-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9689-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9689-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T12:56:24Z","timestamp":1498308984000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9689-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,23]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["9689"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9689-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,23]]}}}