{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T05:59:35Z","timestamp":1772171975236,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T00:00:00Z","timestamp":1615420800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T00:00:00Z","timestamp":1615420800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003447","name":"State Scholarships Foundation","doi-asserted-by":"publisher","award":["MIS-5000432"],"award-info":[{"award-number":["MIS-5000432"]}],"id":[{"id":"10.13039\/501100003447","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013209","name":"Hellenic Foundation for Research and Innovation","doi-asserted-by":"publisher","award":["431"],"award-info":[{"award-number":["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":[[2021,7]]},"DOI":"10.1007\/s00453-021-00817-8","type":"journal-article","created":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T18:02:48Z","timestamp":1615485768000},"page":"2018-2046","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Cluster Deletion on Interval Graphs and Split Related Graphs"],"prefix":"10.1007","volume":"83","author":[{"given":"Athanasios L.","family":"Konstantinidis","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5556-2981","authenticated-orcid":false,"given":"Charis","family":"Papadopoulos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,11]]},"reference":[{"key":"817_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, 89\u2013113 (2004)","journal-title":"Mach. Learn."},{"key":"817_CR2","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1016\/j.ipl.2015.02.007","volume":"115","author":"F Bonomo","year":"2015","unstructured":"Bonomo, F., Dur\u00e1n, G., Napoli, A., Valencia-Pabon, M.: A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to $$P_4$$-sparse graphs. Inf. Proc. Lett. 115, 600\u2013603 (2015)","journal-title":"Inf. Proc. Lett."},{"key":"817_CR3","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. Comput. Science 600, 59\u201369 (2015)","journal-title":"Theor. Comput. Science"},{"key":"817_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"key":"817_CR5","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2013.01.009","volume":"511","author":"B Bui-Xuan","year":"2013","unstructured":"Bui-Xuan, B., Telle, J.A., Vatshelle, M.: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci. 511, 66\u201376 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"817_CR6","first-page":"21","volume":"79","author":"MR Cerioli","year":"2006","unstructured":"Cerioli, M.R., Szwarcfiter, J.L.: Characterizing intersection graphs of substars of a star. ARS Comb. 79, 21\u201331 (2006)","journal-title":"ARS Comb."},{"key":"817_CR7","first-page":"524","volume":"2003","author":"M Charikar","year":"2003","unstructured":"Charikar, M., Guruswami, V., Wirth, A.: Clustering with qualitative information. Proc. FOCS 2003, 524\u2013533 (2003)","journal-title":"Proc. FOCS"},{"key":"817_CR8","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":"817_CR9","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1142\/S0129054107004656","volume":"18","author":"A Dessmark","year":"2007","unstructured":"Dessmark, A., Jansson, J., Lingas, A., Lundell, E., Persson, M.: On the approximability of maximum and minimum edge clique partition problems. Int. J. Found. Comput. Sci. 18, 217\u2013226 (2007)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"817_CR10","first-page":"311","volume":"19","author":"S F\u00f6ldes","year":"1977","unstructured":"F\u00f6ldes, S., Hammer, P.L.: Split graphs. Congr. Numer. 19, 311\u2013315 (1977)","journal-title":"Congr. Numer."},{"key":"817_CR11","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pac. J. Math. 15, 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"key":"817_CR12","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. Discrete Math. 313, 2763\u20132771 (2013)","journal-title":"Discrete Math."},{"key":"817_CR13","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1016\/S0304-3975(02)00725-9","volume":"299","author":"MU Gerber","year":"2003","unstructured":"Gerber, M.U., Kobler, D.: Algorithms for vertex-partitioning problems on graphs with fixed clique-width. Theor. Comput. Sci. 299, 719\u2013734 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"817_CR14","doi-asserted-by":"publisher","first-page":"2006","DOI":"10.1007\/s00453-020-00684-9","volume":"82","author":"PA Golovach","year":"2020","unstructured":"Golovach, P.A., Heggernes, P., Konstantinidis, A.L., Lima, P.T., Papadopoulos, C.: Parameterized aspects of strong subgraph closure. Algorithmica 82(7), 2006\u20132038 (2020)","journal-title":"Algorithmica"},{"key":"817_CR15","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"MC Golumbic","year":"2000","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11, 423\u2013443 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"817_CR16","first-page":"239","volume":"2018","author":"N Gr\u00fcttemeier","year":"2018","unstructured":"Gr\u00fcttemeier, N., Komusiewicz, C.: On the relation of strong triadic closure and cluster deletion. Proc. WG 2018, 239\u2013251 (2018)","journal-title":"Proc. WG"},{"key":"817_CR17","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, 275\u2013284 (1981)","journal-title":"Combinatorica"},{"key":"817_CR18","first-page":"191","volume":"79","author":"P Hansen","year":"1997","unstructured":"Hansen, P., Jaumard, B.: Cluster analysis and mathematical programming. Math. Program. 79, 191\u2013215 (1997)","journal-title":"Math. Program."},{"key":"817_CR19","volume-title":"Clustering Algorithms","author":"J Hartigan","year":"1975","unstructured":"Hartigan, J.: Clustering Algorithms. Wiley, New York (1975)"},{"key":"817_CR20","first-page":"171","volume":"2010","author":"P Heggernes","year":"2010","unstructured":"Heggernes, P., Lokshtanov, D., Nederlof, J., Paul, C., Telle, J.A.: Generalized graph clustering: recognizing $$(p, q)$$-cluster graphs. Proc. WG 2010, 171\u2013183 (2010)","journal-title":"Proc. WG"},{"key":"817_CR21","unstructured":"Kanj, I.A., Komusiewicz, C., Sorge, M., van Leeuwen, E.J.: Solving partition problems almost always requires pushing many vertices around. In: Proceedings of ESA 2018, pp. 51:1\u201351:14 (2018)"},{"key":"817_CR22","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, 2259\u20132270 (2012)","journal-title":"Discrete Appl. Math."},{"key":"817_CR23","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)","journal-title":"Theor. Comput. Sci."},{"key":"817_CR24","unstructured":"Konstantinidis, A.L., Papadopoulos, C.: Cluster deletion on interval graphs and split related graphs. In: Proceedings of MFCS 2019, pp. 12:1\u201312:14 (2019)"},{"key":"817_CR25","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. Discrete Appl. Math. 285, 79\u201395 (2020)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"817_CR26","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","volume":"1","author":"SE Schaeffer","year":"2007","unstructured":"Schaeffer, S.E.: Graph clustering. Comput. Sci. Rev. 1(1), 27\u201364 (2007)","journal-title":"Comput. Sci. Rev."},{"key":"817_CR27","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. Discrete Appl. Math. 144, 173\u2013182 (2004)","journal-title":"Discrete Appl. Math."},{"key":"817_CR28","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"JA Telle","year":"1997","unstructured":"Telle, J.A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math. 10, 529\u2013550 (1997)","journal-title":"SIAM J. Discrete Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00817-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00817-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00817-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,22]],"date-time":"2021-06-22T09:08:03Z","timestamp":1624352883000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00817-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,11]]},"references-count":28,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["817"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00817-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,11]]},"assertion":[{"value":"26 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}