{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T01:17:02Z","timestamp":1780708622754,"version":"3.54.1"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031270505","type":"print"},{"value":"9783031270512","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-27051-2_31","type":"book-chapter","created":{"date-parts":[[2023,3,13]],"date-time":"2023-03-13T00:03:35Z","timestamp":1678665815000},"page":"371-383","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Structural Parameterization of\u00a0Cluster Deletion"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9492-9894","authenticated-orcid":false,"given":"Giuseppe F.","family":"Italiano","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Athanasios L.","family":"Konstantinidis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5556-2981","authenticated-orcid":false,"given":"Charis","family":"Papadopoulos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,3,13]]},"reference":[{"key":"31_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). https:\/\/doi.org\/10.1023\/b:mach.0000033116.57574.95","journal-title":"Mach. Learn."},{"key":"31_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, 281\u2013297 (1999)","journal-title":"J. Comput. Biol."},{"key":"31_CR3","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":"31_CR4","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. Discrete Appl. Math. 231, 78\u201394 (2017)","journal-title":"Discrete Appl. Math."},{"key":"31_CR5","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. Sci. 600, 59\u201369 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"31_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, 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"31_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"},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"Cao, Y., Ke, Y.: Improved kernels for edge modification problems. In: Proceedings of IPEC 2021, pp. 1\u201314 (2021)","DOI":"10.1016\/j.tcs.2021.08.015"},{"key":"31_CR9","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":"31_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., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"31_CR11","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":"31_CR12","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1007\/978-3-642-32589-2","DOI":"10.1007\/978-3-642-32589-2"},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7, 49\u201365 (1987). https:\/\/doi.org\/10.1007\/BF02579200","journal-title":"Combinatorica"},{"key":"31_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/978-3-642-28050-4_21","volume-title":"Parameterized and Exact Computation","author":"R Ganian","year":"2012","unstructured":"Ganian, R.: Twin-cover: beyond vertex cover in parameterized algorithmics. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 259\u2013271. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-28050-4_21"},{"issue":"2","key":"31_CR15","first-page":"77","volume":"17","author":"R Ganian","year":"2015","unstructured":"Ganian, R.: Improving vertex cover as a graph parameter. Discrete Math. Theor. Comput. Sci. 17(2), 77\u2013100 (2015)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"31_CR16","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":"31_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/3-540-44849-7_17","volume-title":"Algorithms and Complexity","author":"J Gramm","year":"2003","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Graph-modeled data clustering: fixed-parameter algorithms for clique generation. In: Petreschi, R., Persiano, G., Silvestri, R. (eds.) CIAC 2003. LNCS, vol. 2653, pp. 108\u2013119. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-44849-7_17"},{"issue":"4","key":"31_CR18","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/s00453-019-00617-1","volume":"82","author":"N Gr\u00fcttemeier","year":"2019","unstructured":"Gr\u00fcttemeier, N., Komusiewicz, C.: On the relation of strong triadic closure and cluster\u00a0deletion. Algorithmica 82(4), 853\u2013880 (2019). https:\/\/doi.org\/10.1007\/s00453-019-00617-1","journal-title":"Algorithmica"},{"key":"31_CR19","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"JHW Lenstra","year":"1983","unstructured":"Lenstra, J.H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"31_CR20","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":"31_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/978-3-642-18381-2_29","volume-title":"SOFSEM 2011: Theory and Practice of Computer Science","author":"C Komusiewicz","year":"2011","unstructured":"Komusiewicz, C., Uhlmann, J.: Alternative parameterizations for cluster editing. In: \u010cern\u00e1, I., et al. (eds.) SOFSEM 2011. LNCS, vol. 6543, pp. 344\u2013355. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-18381-2_29"},{"key":"31_CR22","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":"7","key":"31_CR23","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). https:\/\/doi.org\/10.1007\/s00453-021-00817-8","journal-title":"Algorithmica"},{"issue":"1","key":"31_CR24","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). https:\/\/doi.org\/10.1007\/s00453-011-9554-x","journal-title":"Algorithmica"},{"key":"31_CR25","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. Theor. 66, 3065\u20133078 (2020)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"31_CR26","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":"31_CR27","doi-asserted-by":"publisher","first-page":"106171","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."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-27051-2_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,13]],"date-time":"2023-03-13T00:06:46Z","timestamp":1678666006000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-27051-2_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031270505","9783031270512"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-27051-2_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"13 March 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hsinchu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taiwan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 March 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 March 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.walcom2023.conf.nycu.edu.tw\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easy Chair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"75","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This proceeding includes 2 invited papers.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}