{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T05:58:46Z","timestamp":1772171926879,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2025,3,15]],"date-time":"2025-03-15T00:00:00Z","timestamp":1741996800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,3,15]],"date-time":"2025-03-15T00:00:00Z","timestamp":1741996800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN Project AHeAD"],"award-info":[{"award-number":["PRIN Project AHeAD"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013209","name":"Hellenic Foundation for Research and Innovation","doi-asserted-by":"publisher","award":["HFRI-FM17-431"],"award-info":[{"award-number":["HFRI-FM17-431"]}],"id":[{"id":"10.13039\/501100013209","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s00453-025-01303-1","type":"journal-article","created":{"date-parts":[[2025,3,15]],"date-time":"2025-03-15T08:33:07Z","timestamp":1742027587000},"page":"961-981","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Structural Parameterization of Cluster Deletion"],"prefix":"10.1007","volume":"87","author":[{"given":"Giuseppe F.","family":"Italiano","sequence":"first","affiliation":[]},{"given":"Athanasios L.","family":"Konstantinidis","sequence":"additional","affiliation":[]},{"given":"Charis","family":"Papadopoulos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,15]]},"reference":[{"key":"1303_CR1","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, 281\u2013297 (1999)","journal-title":"J. Comput. Biol."},{"key":"1303_CR2","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, 89\u2013113 (2004)","journal-title":"Mach. Learn."},{"key":"1303_CR3","doi-asserted-by":"publisher","first-page":"3065","DOI":"10.1109\/TIT.2019.2940246","volume":"66","author":"P Li","year":"2020","unstructured":"Li, P., Puleo, G.J., Milenkovic, O.: Motif and hypergraph correlation clustering. IEEE Trans. Inf. Theory 66, 3065\u20133078 (2020)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1303_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.dam.2004.01.007","volume":"144","author":"R Shamir","year":"2004","unstructured":"Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discret. Appl. Math. 144, 173\u2013182 (2004)","journal-title":"Discret. Appl. Math."},{"key":"1303_CR5","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, 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1303_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)","journal-title":"Algorithmica"},{"key":"1303_CR7","unstructured":"Cao, Y., Ke, Y.: Improved Kernels for Edge Modification Problems. In: Proceedings of IPEC 2021, pp. 13\u201311314 (2021)"},{"key":"1303_CR8","doi-asserted-by":"publisher","first-page":"5467","DOI":"10.1016\/j.tcs.2009.05.006","volume":"410","author":"S B\u00f6cker","year":"2009","unstructured":"B\u00f6cker, S., Briesemeister, S., Bui, Q.B.A., Tru\u00df, A.: Going weighted: Parameterized algorithms for cluster editing. Theor. Comput. Sci. 410, 5467\u20135480 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"1303_CR9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2021.106171","volume":"173","author":"D Tsur","year":"2022","unstructured":"Tsur, D.: Cluster deletion revisited. Inf. Process. Lett. 173, 106171 (2022)","journal-title":"Inf. Process. Lett."},{"key":"1303_CR10","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. Discret. Appl. Math. 160, 2259\u20132270 (2012)","journal-title":"Discret. Appl. Math."},{"key":"1303_CR11","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, 853\u2013880 (2020)","journal-title":"Algorithmica"},{"key":"1303_CR12","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.tcs.2015.07.001","volume":"600","author":"F Bonomo","year":"2015","unstructured":"Bonomo, F., Dur\u00e1n, G., Valencia-Pabon, M.: Complexity of the cluster deletion problem on subclasses of chordal graphs. Theor. Comp. Sci. 600, 59\u201369 (2015)","journal-title":"Theor. Comp. Sci."},{"issue":"7","key":"1303_CR13","doi-asserted-by":"publisher","first-page":"2018","DOI":"10.1007\/s00453-021-00817-8","volume":"83","author":"AL Konstantinidis","year":"2021","unstructured":"Konstantinidis, A.L., Papadopoulos, C.: Cluster deletion on interval graphs and split related graphs. Algorithmica 83(7), 2018\u20132046 (2021)","journal-title":"Algorithmica"},{"key":"1303_CR14","doi-asserted-by":"publisher","first-page":"2763","DOI":"10.1016\/j.disc.2013.08.017","volume":"313","author":"Y Gao","year":"2013","unstructured":"Gao, Y., Hare, D.R., Nastos, J.: The cluster deletion problem for cographs. Discret. Math. 313, 2763\u20132771 (2013)","journal-title":"Discret. Math."},{"key":"1303_CR15","doi-asserted-by":"crossref","unstructured":"Komusiewicz, C., Uhlmann, J.: Alternative parameterizations for cluster editing. In: Proceedings of SOFSEM 2011, vol. 6543, pp. 344\u2013355 (2011)","DOI":"10.1007\/978-3-642-18381-2_29"},{"key":"1303_CR16","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.dam.2016.11.016","volume":"231","author":"\u00c9 Bonnet","year":"2017","unstructured":"Bonnet, \u00c9., Sikora, F.: The graph motif problem parameterized by the structure of the input graph. Discret. Appl. Math. 231, 78\u201394 (2017)","journal-title":"Discret. Appl. Math."},{"key":"1303_CR17","doi-asserted-by":"crossref","unstructured":"Ganian, R.: Twin-cover: Beyond vertex cover in parameterized algorithmics. In: Parameterized and Exact Computation, pp. 259\u2013271 (2012)","DOI":"10.1007\/978-3-642-28050-4_21"},{"key":"1303_CR18","doi-asserted-by":"crossref","unstructured":"Ganian, R.: Improving vertex cover as a graph parameter. Discrete Math. Theor. Comput. Sci. 17(2), (2015)","DOI":"10.46298\/dmtcs.2136"},{"issue":"1","key":"1303_CR19","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00453-011-9554-x","volume":"64","author":"M Lampis","year":"2012","unstructured":"Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64(1), 19\u201337 (2012)","journal-title":"Algorithmica"},{"key":"1303_CR20","doi-asserted-by":"crossref","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Graph-modeled data clustering: Fixed-parameter algorithms for clique generation. In: Proceedings of CIAC 2003, vol. 2653, pp. 108\u2013119 (2003)","DOI":"10.1007\/3-540-44849-7_17"},{"key":"1303_CR21","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.dam.2020.05.035","volume":"285","author":"AL Konstantinidis","year":"2020","unstructured":"Konstantinidis, A.L., Papadopoulos, C.: Maximizing the strong triadic closure in split graphs and proper interval graphs. Discret. Appl. Math. 285, 79\u201395 (2020)","journal-title":"Discret. Appl. Math."},{"key":"1303_CR22","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I: recognizable sets of finite graphs. Inf. Comput. 85, 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"1303_CR23","doi-asserted-by":"crossref","unstructured":"Doucha, M., Kratochv\u00edl, J.: Cluster vertex deletion: a parameterization between vertex cover and clique-width. In: Proceedings of MFCS 2012, vol. 7464, pp. 348\u2013359 (2012)","DOI":"10.1007\/978-3-642-32589-2_32"},{"issue":"10","key":"1303_CR24","doi-asserted-by":"publisher","first-page":"2902","DOI":"10.1007\/s00453-020-00708-4","volume":"82","author":"D Majumdar","year":"2020","unstructured":"Majumdar, D., Ramanujan, M.S., Saurabh, S.: On the approximate compressibility of connected vertex cover. Algorithmica 82(10), 2902\u20132926 (2020)","journal-title":"Algorithmica"},{"key":"1303_CR25","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, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"1303_CR26","doi-asserted-by":"crossref","unstructured":"Tedder, M., Corneil, D.G., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: Proceedings of ICALP 2008. Lecture Notes in Computer Science, vol. 5125, pp. 634\u2013645 (2008)","DOI":"10.1007\/978-3-540-70575-8_52"},{"issue":"40","key":"1303_CR27","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoret. Comput. Sci. 411(40), 3736\u20133756 (2010). https:\/\/doi.org\/10.1016\/j.tcs.2010.06.026","journal-title":"Theoret. Comput. Sci."},{"key":"1303_CR28","doi-asserted-by":"crossref","unstructured":"Gajarsk\u00fd, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Parameterized and Exact Computation (2013)","DOI":"10.1007\/978-3-319-03898-8_15"},{"key":"1303_CR29","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math. 101, 77\u2013114 (2000)","journal-title":"Discret. Appl. Math."},{"key":"1303_CR30","doi-asserted-by":"publisher","first-page":"1146","DOI":"10.1007\/s00453-017-0297-1","volume":"80","author":"FV Fomin","year":"2018","unstructured":"Fomin, F.V., Liedloff, M., Montealegre, P., Todinca, I.: Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. Algorithmica 80, 1146\u20131169 (2018)","journal-title":"Algorithmica"},{"key":"1303_CR31","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23, 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"1303_CR32","volume-title":"Threshold Graphs and Related Topics","author":"NVR Mahadev","year":"1996","unstructured":"Mahadev, N.V.R., Peled, U.N.: Threshold Graphs and Related Topics, vol. 56. Annals of Discrete Mathematics, Amsterdam (1996)"},{"key":"1303_CR33","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"1303_CR34","first-page":"49","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Comb. 7, 49\u201365 (1987)","journal-title":"Comb."},{"key":"1303_CR35","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, 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"1303_CR36","unstructured":"Blazej, V., Choudhary, P., Knop, D., Schierreich, S., Such\u00fd, O., Valla, T.: On polynomial kernels for traveling salesperson problem and its generalizations. In: Proceedings of ESA 2022. LIPIcs, vol. 244, pp. 22\u201312216 (2022)"},{"issue":"11","key":"1303_CR37","doi-asserted-by":"publisher","first-page":"3300","DOI":"10.1007\/s00453-022-00965-5","volume":"84","author":"\u00c9 Bonnet","year":"2022","unstructured":"Bonnet, \u00c9., Kim, E.J., Reinald, A., Thomass\u00e9, S., Watrigant, R.: Twin-width and polynomial kernels. Algorithmica 84(11), 3300\u20133337 (2022)","journal-title":"Algorithmica"},{"key":"1303_CR38","doi-asserted-by":"crossref","unstructured":"Lafond, M., Luo, W.: Preprocessing complexity for some graph problems parameterized by structural parameters. In: Proceedings of LAGOS 2023. Procedia Computer Science, vol. 223, pp. 130\u2013139 (2023)","DOI":"10.1016\/j.procs.2023.08.222"},{"key":"1303_CR39","doi-asserted-by":"crossref","unstructured":"Italiano, G.F., Konstantinidis, A.L., Papadopoulos, C.: Structural parameterization of cluster deletion. In: Proceedings of WALCOM 2023. Lecture Notes in Computer Science, vol. 13973, pp. 371\u2013383 (2023)","DOI":"10.1007\/978-3-031-27051-2_31"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01303-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01303-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01303-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T11:23:27Z","timestamp":1747135407000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01303-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,15]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["1303"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01303-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,15]]},"assertion":[{"value":"31 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics Approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to Participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}},{"value":"Not applicable.","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code Availability"}}]}}