{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:20:24Z","timestamp":1761621624301,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2022,5,3]],"date-time":"2022-05-03T00:00:00Z","timestamp":1651536000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,5,3]],"date-time":"2022-05-03T00:00:00Z","timestamp":1651536000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-CE40-0032"],"award-info":[{"award-number":["ANR-18-CE40-0032"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["15201317","15226116"],"award-info":[{"award-number":["15201317","15226116"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014717","name":"National Outstanding Youth Science Fund Project of National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["1972330"],"award-info":[{"award-number":["1972330"]}],"id":[{"id":"10.13039\/100014717","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s00453-022-00969-1","type":"journal-article","created":{"date-parts":[[2022,5,3]],"date-time":"2022-05-03T07:03:57Z","timestamp":1651561437000},"page":"3338-3364","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["(Sub)linear Kernels for Edge Modification Problems Toward Structured Graph Classes"],"prefix":"10.1007","volume":"84","author":[{"given":"Gabriel","family":"Bathie","sequence":"first","affiliation":[]},{"given":"Nicolas","family":"Bousquet","sequence":"additional","affiliation":[]},{"given":"Yixin","family":"Cao","sequence":"additional","affiliation":[]},{"given":"Yuping","family":"Ke","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5586-5613","authenticated-orcid":false,"given":"Th\u00e9o","family":"Pierron","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,3]]},"reference":[{"issue":"1","key":"969_CR1","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N Bansal","year":"2004","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1), 89\u2013113 (2004)","journal-title":"Mach. Learn."},{"issue":"3\u20134","key":"969_CR2","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1089\/106652799318274","volume":"6","author":"A Ben-Dor","year":"1999","unstructured":"Ben-Dor, A., Shamir, R., Yakhini, Z.: Clustering gene expression patterns. J. Comput. Biol. 6(3\u20134), 281\u2013297 (1999)","journal-title":"J. Comput. Biol."},{"key":"969_CR3","doi-asserted-by":"crossref","unstructured":"Bliznets, I., Cygan, M., Komosa, P., Mach, L., Pilipczuk, M.: Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1132\u20131151. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch79"},{"key":"969_CR4","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jda.2012.04.005","volume":"16","author":"S B\u00f6cker","year":"2012","unstructured":"B\u00f6cker, S.: A golden ratio parameterized algorithm for cluster editing. J. Discrete Algorithms 16, 79\u201389 (2012)","journal-title":"J. Discrete Algorithms"},{"issue":"13","key":"969_CR5","doi-asserted-by":"publisher","first-page":"1824","DOI":"10.1016\/j.dam.2006.03.031","volume":"154","author":"P Burzyn","year":"2006","unstructured":"Burzyn, P., Bonomo, F., Dur\u00e1n, G.: NP-completeness results for edge modification problems. Discrete Appl. Math. 154(13), 1824\u20131844 (2006)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"969_CR6","doi-asserted-by":"publisher","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":"1","key":"969_CR7","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":"1","key":"969_CR8","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.jcss.2011.04.001","volume":"78","author":"J Chen","year":"2012","unstructured":"Chen, J., Meng, J.: A $$2k$$ kernel for the cluster editing problem. J. Comput. Syst. Sci. 78(1), 211\u2013220 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"969_CR9","unstructured":"Crespelle, C., Drange, P., Fomin, F.V., Golovach, P.A.: A survey of parameterized algorithms and the complexity of edge modification. arXiv preprint, arXiv:2001.06867 (2020)"},{"key":"969_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, vol. 5. Springer, Berlin (2015)"},{"issue":"4","key":"969_CR11","doi-asserted-by":"publisher","first-page":"557","DOI":"10.7155\/jgaa.00337","volume":"18","author":"P Damaschke","year":"2014","unstructured":"Damaschke, P., Mogren, O.: Editing simple graphs. J. Graph Algorithms Appl. 18(4), 557\u2013576 (2014). https:\/\/doi.org\/10.7155\/jgaa.00337","journal-title":"J. Graph Algorithms Appl."},{"key":"969_CR12","unstructured":"Drange, P.: Parameterized graph modification algorithms. Ph.D. thesis, University of Bergen (2015)"},{"issue":"4","key":"969_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2799640","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. ACM Trans. Comput. Theory (TOCT) 7(4), 1\u201338 (2015)","journal-title":"ACM Trans. Comput. Theory (TOCT)"},{"issue":"12","key":"969_CR14","doi-asserted-by":"publisher","first-page":"3481","DOI":"10.1007\/s00453-017-0401-6","volume":"80","author":"P Drange","year":"2018","unstructured":"Drange, P., Pilipczuk, M.: A polynomial kernel for trivially perfect editing. Algorithmica 80(12), 3481\u20133524 (2018)","journal-title":"Algorithmica"},{"key":"969_CR15","unstructured":"Drange, P., Reidl, F., Villaamil, F.S., Sikdar, S.: Fast biclustering by dual parameterization. arXiv preprint, arXiv:1507.08158 (2015)"},{"key":"969_CR16","doi-asserted-by":"publisher","unstructured":"Dumas, M., Perez, A., Todinca, I.: A cubic vertex-kernel for trivially perfect editing. In: 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, 23\u201327 August 2021, Tallinn, Estonia, LIPIcs, vol. 202, pp. 45:1\u201345:14. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2021.45","DOI":"10.4230\/LIPIcs.MFCS.2021.45"},{"issue":"7","key":"969_CR17","doi-asserted-by":"publisher","first-page":"1430","DOI":"10.1016\/j.jcss.2014.04.015","volume":"80","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Kratsch, S., Pilipczuk, M., Pilipczuk, M., Villanger, Y.: Tight bounds for parameterized complexity of cluster editing with a small number of clusters. J. Comput. Syst. Sci. 80(7), 1430\u20131447 (2014)","journal-title":"J. Comput. Syst. Sci."},{"key":"969_CR18","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2019)"},{"issue":"4","key":"969_CR19","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1007\/s00453-013-9837-5","volume":"71","author":"E Ghosh","year":"2015","unstructured":"Ghosh, E., Kolay, S., Kumar, M., Misra, P., Panolan, F., Rai, A., Ramanujan, M.S.: Faster parameterized algorithms for deletion to split graphs. Algorithmica 71(4), 989\u20131006 (2015)","journal-title":"Algorithmica"},{"issue":"4","key":"969_CR20","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/s00453-019-00617-1","volume":"82","author":"N Gr\u00fcttemeier","year":"2020","unstructured":"Gr\u00fcttemeier, N., Komusiewicz, C.: On the relation of strong triadic closure and cluster deletion. Algorithmica 82(4), 853\u2013880 (2020). https:\/\/doi.org\/10.1007\/s00453-019-00617-1","journal-title":"Algorithmica"},{"key":"969_CR21","doi-asserted-by":"crossref","unstructured":"Guo, J.: Problem kernels for NP-complete edge deletion problems: split and related graphs. In: International Symposium on Algorithms and Computation, pp. 915\u2013926. Springer (2007)","DOI":"10.1007\/978-3-540-77120-3_79"},{"issue":"3","key":"969_CR22","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/BF02579333","volume":"1","author":"PL Hammer","year":"1981","unstructured":"Hammer, P.L., Simeone, B.: The splittance of a graph. Combinatorica 1(3), 275\u2013284 (1981)","journal-title":"Combinatorica"},{"issue":"2","key":"969_CR23","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":"15","key":"969_CR24","doi-asserted-by":"publisher","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":"969_CR25","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.tcs.2018.05.012","volume":"740","author":"AL Konstantinidis","year":"2018","unstructured":"Konstantinidis, A.L., Nikolopoulos, S.D., Papadopoulos, C.: Strong triadic closure in cographs and graphs of low maximum degree. Theor. Comput. Sci. 740, 76\u201384 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2018.05.012","journal-title":"Theor. Comput. Sci."},{"key":"969_CR26","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.tcs.2015.01.049","volume":"573","author":"Y Liu","year":"2015","unstructured":"Liu, Y., Wang, J., You, J., Chen, J., Cao, Y.: Edge deletion problems: branching facilitated by modular decomposition. Theor. Comput. Sci. 573, 63\u201370 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"969_CR27","unstructured":"Mancini, F.: Graph modification problems related to graph classes. Ph.D. thesis, University of Bergen (2008)"},{"issue":"1","key":"969_CR28","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0166-218X(00)00391-7","volume":"113","author":"A Natanzon","year":"2001","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Appl. Math. 113(1), 109\u2013128 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"969_CR29","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1007\/s00224-016-9746-5","volume":"62","author":"R van Bevern","year":"2018","unstructured":"van Bevern, R., Froese, V., Komusiewicz, C.: Parameterizing edge modification problems above lower bounds. Theory Comput. Syst. 62(3), 739\u2013770 (2018)","journal-title":"Theory Comput. Syst."},{"key":"969_CR30","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1090\/S0002-9939-1962-0172273-0","volume":"13","author":"ES Wolk","year":"1962","unstructured":"Wolk, E.S.: The comparability graph of a tree. Proc. Am. Math. Soc. 13, 789\u2013795 (1962). https:\/\/doi.org\/10.1090\/S0002-9939-1962-0172273-0","journal-title":"Proc. Am. Math. Soc."},{"issue":"11","key":"969_CR31","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.1109\/34.244673","volume":"15","author":"W Zhenyu","year":"1993","unstructured":"Zhenyu, W., Leahy, R.: An optimal graph theoretic approach to data clustering: theory and its application to image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 15(11), 1101\u20131113 (1993)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"3","key":"969_CR32","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0166-218X(96)00094-7","volume":"69","author":"J-H Yan","year":"1996","unstructured":"Yan, J.-H., Chen, J.-J., Chang, G.J.: Quasi-threshold graphs. Discrete Appl. Math. 69(3), 247\u2013255 (1996). https:\/\/doi.org\/10.1016\/0166-218X(96)00094-7","journal-title":"Discrete Appl. Math."},{"key":"969_CR33","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 253\u2013264 (1978)","DOI":"10.1145\/800133.804355"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00969-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00969-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00969-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,25]],"date-time":"2022-10-25T12:23:20Z","timestamp":1666700600000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00969-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,3]]},"references-count":33,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["969"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00969-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,5,3]]},"assertion":[{"value":"1 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}