{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,26]],"date-time":"2026-01-26T07:08:56Z","timestamp":1769411336128,"version":"3.49.0"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T00:00:00Z","timestamp":1762819200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T00:00:00Z","timestamp":1762819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62372095"],"award-info":[{"award-number":["62372095"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSERC Discovery Research Grant","award":["RGPIN-2018-06800"],"award-info":[{"award-number":["RGPIN-2018-06800"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s00224-025-10247-6","type":"journal-article","created":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T02:22:08Z","timestamp":1762827728000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improved Parameterized Algorithms for Cluster Vertex Deletion"],"prefix":"10.1007","volume":"69","author":[{"given":"Kangyi","family":"Tian","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1012-2373","authenticated-orcid":false,"given":"Mingyu","family":"Xiao","sequence":"additional","affiliation":[]},{"given":"Boting","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,11,11]]},"reference":[{"issue":"1\u20133","key":"10247_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\u20133), 89\u2013113 (2004)","journal-title":"Mach. Learn."},{"issue":"3\/4","key":"10247_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\/4), 281\u2013297 (1999)","journal-title":"J. Comput. Biol."},{"key":"10247_CR3","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 Algo. 16, 79\u201389 (2012)","journal-title":"J. Discrete Algo."},{"issue":"52","key":"10247_CR4","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(52), 5467\u20135480 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10247_CR5","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s00224-015-9631-7","volume":"58","author":"A Boral","year":"2016","unstructured":"Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: A fast branching algorithm for cluster vertex deletion. Theory Comput. Syst. 58(2), 357\u2013376 (2016)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"10247_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."},{"key":"10247_CR7","volume-title":"D\u00e1niel Marx","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D.: D\u00e1niel Marx. Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, Marcin Pilipczuk (2015)"},{"key":"10247_CR8","doi-asserted-by":"crossref","unstructured":"Peter, D.: Bounded-degree techniques accelerate some parameterized graph algorithms. In: Jianer, C., Fedor,\u00a0V. F., editors, Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, 10-11 September, 2009, Revised Selected Papers, volume 5917 of Lecture Notes in Computer Science, pp. 98\u2013109. Springer, (2009)","DOI":"10.1007\/978-3-642-11269-0_8"},{"key":"10247_CR9","doi-asserted-by":"crossref","unstructured":"Fedor,\u00a0V. F., Serge, G., Daniel, L., Saket, S.: Exact algorithms via monotone local search. In: Daniel, W., Yishay, M., editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, 18-21 June, 2016, pp. 764\u2013775. ACM, (2016)","DOI":"10.1145\/2897518.2897551"},{"issue":"4","key":"10247_CR10","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s00453-004-1090-5","volume":"39","author":"J Gramm","year":"2004","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39(4), 321\u2013347 (2004)","journal-title":"Algorithmica"},{"issue":"4","key":"10247_CR11","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00224-004-1178-y","volume":"38","author":"J Gramm","year":"2005","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Graph-modeled data clustering: exact algorithms for clique generation. Theory Comput. Syst. 38(4), 373\u2013392 (2005)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"10247_CR12","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/s00224-008-9150-x","volume":"47","author":"F H\u00fcffner","year":"2010","unstructured":"H\u00fcffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-parameter algorithms for cluster vertex deletion. Theory Comput. Syst. 47(1), 196\u2013217 (2010)","journal-title":"Theory Comput. Syst."},{"key":"10247_CR13","doi-asserted-by":"crossref","unstructured":"Kangyi, T., Mingyu, X., Boting, Y.: Parameterized algorithms for cluster vertex deletion on degree-4 graphs and general graphs. In: Weili, W., Guangmo, T., editors, Computing and Combinatorics - 29th International Conference, COCOON 2023, Hawaii, HI, USA, 15-17 December, 2023, Proceedings, Part I, volume 14422 of Lecture Notes in Computer Science, pp. 182\u2013194. Springer, (2023)","DOI":"10.1007\/978-3-031-49190-0_13"},{"key":"10247_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.03.013","volume":"783","author":"D Tsur","year":"2019","unstructured":"Tsur, D.: Parameterized algorithm for 3-path vertex cover. Theor. Comput. Sci. 783, 1\u20138 (2019)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10247_CR15","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s00224-020-10005-w","volume":"65","author":"D Tsur","year":"2021","unstructured":"Tsur, D.: Faster parameterized algorithm for cluster vertex deletion. Theory Comput. Syst. 65(2), 323\u2013343 (2021)","journal-title":"Theory Comput. Syst."},{"key":"10247_CR16","doi-asserted-by":"crossref","unstructured":"Tsur, D.: Cluster deletion revisited. Inf. Process. Lett. 173, 106171 (2022)","DOI":"10.1016\/j.ipl.2021.106171"},{"key":"10247_CR17","unstructured":"Magnus, W.: Algorithms, measures and upper bounds for satisfiability and related problems. PhD thesis, Link\u00f6ping University, Sweden, (2007)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10247-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10247-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10247-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T08:52:44Z","timestamp":1769244764000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10247-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,11]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10247"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10247-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,11]]},"assertion":[{"value":"8 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 November 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":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"37"}}