{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T21:09:49Z","timestamp":1766178589897,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T00:00:00Z","timestamp":1655856000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T00:00:00Z","timestamp":1655856000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"publisher","award":["SRG\/2019\/002276"],"award-info":[{"award-number":["SRG\/2019\/002276"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009935","name":"Indo-French Centre for Applied Mathematics","doi-asserted-by":"publisher","award":["MA\/IFCAM\/18\/39"],"award-info":[{"award-number":["MA\/IFCAM\/18\/39"]}],"id":[{"id":"10.13039\/100009935","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s00453-022-00991-3","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T22:02:50Z","timestamp":1655935370000},"page":"2842-2870","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On Subgraph Complementation to H-free Graphs"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7875-3457","authenticated-orcid":false,"given":"Dhanyamol","family":"Antony","sequence":"first","affiliation":[]},{"given":"Jay","family":"Garchar","sequence":"additional","affiliation":[]},{"given":"Sagartanu","family":"Pal","sequence":"additional","affiliation":[]},{"given":"R. B.","family":"Sandeep","sequence":"additional","affiliation":[]},{"given":"Sagnik","family":"Sen","sequence":"additional","affiliation":[]},{"given":"R.","family":"Subashini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"key":"991_CR1","doi-asserted-by":"publisher","unstructured":"Antony, D., Garchar, J., Pal, S., Sandeep, R.B., Sen, S., Subashini, R.: On subgraph complementation to H-free graphs. In: Kowalik, L., Pilipczuk, M., Rzazewski, P. (eds.), Graph-Theoretic Concepts in Computer Science\u201447th International Workshop, WG 2021, Warsaw, Poland, June 23\u201325, 2021, Revised Selected Papers. Lecture Notes in Computer Science, vol. 12911, pp. 118\u2013129. Springer, (2021). https:\/\/doi.org\/10.1007\/978-3-030-86838-3_9","DOI":"10.1007\/978-3-030-86838-3_9"},{"issue":"1","key":"991_CR2","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1137\/16M1055797","volume":"31","author":"NR Aravind","year":"2017","unstructured":"Aravind, N.R., Sandeep, R.B., Sivadasan, N.: Dichotomy results on the hardness of H-free edge modification problems. SIAM J. Discrete Math. 31(1), 542\u2013561 (2017). https:\/\/doi.org\/10.1137\/16M1055797","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"991_CR3","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/s00453-014-9937-x","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). https:\/\/doi.org\/10.1007\/s00453-014-9937-x","journal-title":"Algorithmica"},{"key":"991_CR4","unstructured":"Cai, Y.: Polynomial kernelisation of H-free edge modification problems. M.Phil. Thesis, Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong SAR, China (2012)"},{"issue":"8\u201310","key":"991_CR5","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. Comput. Sci. 410(8\u201310), 718\u2013726 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2008.10.021","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"991_CR6","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/s00453-011-9595-1","volume":"64","author":"Y Cao","year":"2012","unstructured":"Cao, Y., Chen, J.: Cluster editing: kernelization based on edge cuts. Algorithmica 64(1), 152\u2013169 (2012). https:\/\/doi.org\/10.1007\/s00453-011-9595-1","journal-title":"Algorithmica"},{"issue":"4","key":"991_CR7","doi-asserted-by":"publisher","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_\\ell $$-free edge modification problems. Algorithmica 65(4), 900\u2013926 (2013). https:\/\/doi.org\/10.1007\/s00453-012-9619-5","journal-title":"Algorithmica"},{"key":"991_CR8","doi-asserted-by":"publisher","unstructured":"Cao, Y., Ke, Y., Yuan, H.: Polynomial kernels for paw-free edge modification problems. In: Chen, J., Feng, Q., Xu, J. (eds.) Theory and Applications of Models of Computation, 16th International Conference, TAMC 2020, Changsha, China, October 18\u201320, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12337, pp. 37\u201349, Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-59267-7_4","DOI":"10.1007\/978-3-030-59267-7_4"},{"key":"991_CR9","doi-asserted-by":"publisher","unstructured":"Eiben, E., Lochet, W., Saurabh, S.: A polynomial kernel for paw-free editing. In: Cao, Y., Pilipczuk, M. (eds.) 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14\u201318, 2020, Hong Kong, China (Virtual Conference). LIPIcs, vol. 180, pp. 10:1\u201310:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2020.10","DOI":"10.4230\/LIPIcs.IPEC.2020.10"},{"issue":"2","key":"991_CR10","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1137\/0210021","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10(2), 297\u2013309 (1981). https:\/\/doi.org\/10.1137\/0210021","journal-title":"SIAM J. Comput."},{"issue":"4","key":"991_CR11","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1002\/jgt.21745","volume":"75","author":"E Jel\u00ednkov\u00e1","year":"2014","unstructured":"Jel\u00ednkov\u00e1, E., Kratochv\u00edl, J.: On switching to H-free graphs. J. Graph Theory 75(4), 387\u2013405 (2014). https:\/\/doi.org\/10.1002\/jgt.21745","journal-title":"J. Graph Theory"},{"key":"991_CR12","doi-asserted-by":"publisher","first-page":"104514","DOI":"10.1016\/j.ic.2020.104514","volume":"271","author":"Y Cao","year":"2020","unstructured":"Cao, Y., Sandeep, R.B.: Minimum fill-in: inapproximability and almost tight lower bounds. Inf. Comput. 271, 104514 (2020). https:\/\/doi.org\/10.1016\/j.ic.2020.104514","journal-title":"Inf. Comput."},{"issue":"12","key":"991_CR13","doi-asserted-by":"publisher","first-page":"2747","DOI":"10.1016\/j.dam.2008.08.022","volume":"157","author":"M Kaminski","year":"2009","unstructured":"Kaminski, M., Lozin, V.V., Milanic, M.: Recent developments on graphs of bounded clique-width. Discret. Appl. Math. 157(12), 2747\u20132761 (2009). https:\/\/doi.org\/10.1016\/j.dam.2008.08.022","journal-title":"Discret. Appl. Math."},{"issue":"7","key":"991_CR14","doi-asserted-by":"publisher","first-page":"1859","DOI":"10.1007\/s00453-020-00677-8","volume":"82","author":"FV Fomin","year":"2020","unstructured":"Fomin, F.V., Golovach, P.A., Str\u00f8mme, T.J.F., Thilikos, D.M.: Subgraph complementation. Algorithmica 82(7), 1859\u20131880 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00677-8","journal-title":"Algorithmica"},{"key":"991_CR15","doi-asserted-by":"publisher","unstructured":"Kolay, S., Panolan, F.: Parameterized algorithms for deletion to $$(r, \\ell )$$-graphs. In: Harsha, P., Ramalingam, G. (eds.) 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015. LIPIcs, vol. 45, pp. 420\u2013433. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2015). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2015.420","DOI":"10.4230\/LIPIcs.FSTTCS.2015.420"},{"key":"991_CR16","doi-asserted-by":"publisher","unstructured":"Marx, D., Sandeep, R.B.: Incompressibility of H-free edge modification problems: towards a dichotomy. In: 28th Annual European Symposium on Algorithms, ESA 2020. LIPIcs, vol. 173, pp. 72:1\u201372:25. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.72","DOI":"10.4230\/LIPIcs.ESA.2020.72"},{"key":"991_CR17","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall (2000)"},{"issue":"4","key":"991_CR18","doi-asserted-by":"publisher","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":"991_CR19","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). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"2","key":"991_CR20","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1006\/jcta.1997.2833","volume":"81","author":"A Gy\u00e1rf\u00e1s","year":"1998","unstructured":"Gy\u00e1rf\u00e1s, A.: Generalized split graphs and Ramsey numbers. J. Comb. Theory Ser. A 81(2), 255\u2013261 (1998). https:\/\/doi.org\/10.1006\/jcta.1997.2833","journal-title":"J. Comb. Theory Ser. A"},{"key":"991_CR21","unstructured":"Kolay, S., Panolan, F.: Parameterized algorithms for deletion to (r, l)-graphs. CoRR (2015). arXiv:1504.08120"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00991-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00991-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00991-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T14:19:35Z","timestamp":1664547575000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00991-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,22]]},"references-count":21,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["991"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00991-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,6,22]]},"assertion":[{"value":"6 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}