{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T02:39:16Z","timestamp":1742956756576,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030738785"},{"type":"electronic","value":"9783030738792"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-73879-2_24","type":"book-chapter","created":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T23:04:59Z","timestamp":1620169499000},"page":"340-353","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem"],"prefix":"10.1007","author":[{"given":"Manuel","family":"Aprile","sequence":"first","affiliation":[]},{"given":"Matthew","family":"Drescher","sequence":"additional","affiliation":[]},{"given":"Samuel","family":"Fiorini","sequence":"additional","affiliation":[]},{"given":"Tony","family":"Huynh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,5]]},"reference":[{"issue":"6794","key":"24_CR1","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1038\/35019019","volume":"406","author":"R Albert","year":"2000","unstructured":"Albert, R., Jeong, H., Barab\u00e1si, A.-L.: Error and attack tolerance of complex networks. Nature 406(6794), 378\u2013382 (2000)","journal-title":"Nature"},{"issue":"1","key":"24_CR2","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1111\/itor.12562","volume":"26","author":"M Aprile","year":"2019","unstructured":"Aprile, M., Castro, N., Ferreira, G., Piccini, J., Robledo, F., Romero, P.: Graph fragmentation problem: analysis and synthesis. Int. Trans. Oper. Res. 26(1), 41\u201353 (2019)","journal-title":"Int. Trans. Oper. Res."},{"key":"24_CR3","unstructured":"Aprile, M., Drescher, M., Fiorini, S., Huynh, T.: A simple 7\/3-approximation algorithm for feedback vertex set in tournaments. arXiv preprint arXiv:2008.08779 (2020)"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"Aprile, M., Drescher, M., Fiorini, S., Huynh, T.: A tight approximation algorithm for the cluster vertex deletion problem. arXiv preprint arXiv:2007.08057 (2020)","DOI":"10.1007\/978-3-030-73879-2_24"},{"issue":"1","key":"24_CR5","first-page":"147","volume":"44","author":"A Bazzi","year":"2019","unstructured":"Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No small linear program approximates vertex cover within a factor $$2 - \\epsilon $$. Math. Oper. Res. 44(1), 147\u2013172 (2019)","journal-title":"Math. Oper. Res."},{"key":"24_CR6","series-title":"The IMA Volumes in Mathematics and its Applications","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8369-7_1","volume-title":"Graph Theory and Sparse Matrix Computation","author":"JRS Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory and Sparse Matrix Computation. The IMA Volumes in Mathematics and its Applications, vol. 56. Springer, New York (1993). https:\/\/doi.org\/10.1007\/978-1-4613-8369-7_1"},{"issue":"2","key":"24_CR7","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. Theor. Comput. Syst. 58(2), 357\u2013376 (2016)","journal-title":"Theor. Comput. Syst."},{"issue":"6","key":"24_CR8","doi-asserted-by":"publisher","first-page":"1993","DOI":"10.1137\/S0097539798338163","volume":"30","author":"M-C Cai","year":"2001","unstructured":"Cai, M.-C., Deng, X., Zang, W.: An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput. 30(6), 1993\u20132007 (2001)","journal-title":"SIAM J. Comput."},{"key":"24_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-319-33461-5_20","volume-title":"Integer Programming and Combinatorial Optimization","author":"S Fiorini","year":"2016","unstructured":"Fiorini, S., Joret, G., Schaudt, O.: Improved approximation algorithms for hitting 3-vertex paths. In: Louveaux, Q., Skutella, M. (eds.) IPCO 2016. LNCS, vol. 9682, pp. 238\u2013249. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-33461-5_20"},{"issue":"1\u20132, Ser. A","key":"24_CR10","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s10107-019-01395-y","volume":"182","author":"S Fiorini","year":"2020","unstructured":"Fiorini, S., Joret, G., Schaudt, O.: Improved approximation algorithms for hitting 3-vertex paths. Math. Program. 182(1\u20132, Ser. A), 355\u2013367 (2020)","journal-title":"Math. Program."},{"issue":"2","key":"24_CR11","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/3284176","volume":"66","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Gaspers, S., Lokshtanov, D., Saurabh, S.: Exact algorithms via monotone local search. J. ACM 66(2), 23 (2019)","journal-title":"J. ACM"},{"issue":"1","key":"24_CR12","first-page":"13:1","volume":"15","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Le, T., Lokshtanov, D., Saurabh, S., Thomass\u00e9, S., Zehavi, M.: Subquadratic kernels for implicit 3-hitting set and 3-set packing problems. ACM Trans. Algorithms 15(1), 13:1\u201313:44 (2019)","journal-title":"ACM Trans. Algorithms"},{"key":"24_CR13","first-page":"422","volume":"36","author":"A Freund","year":"2005","unstructured":"Freund, A., Bar-Yehuda, R., Bendel, K.: Local ratio: a unified framework for approximation algorithms. ACM Comput. Surv. 36, 422\u2013463 (2005)","journal-title":"ACM Comput. Surv."},{"key":"24_CR14","unstructured":"Hosseinian, S., Butenko, S.: Polyhedral properties of the induced cluster subgraphs. arXiv preprint arXiv:1904.12025 (2019)"},{"issue":"1","key":"24_CR15","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. Theor. Comput. Syst. 47(1), 196\u2013217 (2010)","journal-title":"Theor. Comput. Syst."},{"issue":"12","key":"24_CR16","doi-asserted-by":"publisher","first-page":"3458","DOI":"10.1016\/j.cnsns.2013.04.030","volume":"18","author":"E Jahanpour","year":"2013","unstructured":"Jahanpour, E., Chen, X.: Analysis of complex network performance and heuristic node removal strategies. Commun. Nonlinear Sci. Numer. Simul. 18(12), 3458\u20133468 (2013)","journal-title":"Commun. Nonlinear Sci. Numer. Simul."},{"key":"24_CR17","unstructured":"Lokshtanov, D.: Personal communication"},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Misra, P., Mukherjee, J., Panolan, F., Philip, G., Saurabh, S.: $$2$$-approximating feedback vertex set in tournaments. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1010\u20131018. SIAM (2020)","DOI":"10.1137\/1.9781611975994.61"},{"key":"24_CR19","unstructured":"Mnich, M., Williams, V.V., V\u00e9gh, L.A.: A 7\/3-approximation for feedback vertex sets in tournaments. In: Sankowski, P., Zaroliagis, C.D. (eds.) 24th Annual European Symposium on Algorithms, ESA 2016. LIPICS, Aarhus, Denmark, 22\u201324 August 2016, vol. 57, pp. 67:1\u201367:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"issue":"3","key":"24_CR20","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3), 411\u2013430 (1990)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"24_CR21","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Decomposition by clique separators. Discret. Math. 55(2), 221\u2013232 (1985)","journal-title":"Discret. Math."},{"issue":"3","key":"24_CR22","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"RE Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3), 566\u2013579 (1984)","journal-title":"SIAM J. Comput."},{"key":"24_CR23","doi-asserted-by":"crossref","unstructured":"Tsur, D.: Faster parameterized algorithm for cluster vertex deletion. CoRR, abs\/1901.07609 (2019)","DOI":"10.1016\/j.ipl.2019.03.009"},{"key":"24_CR24","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1016\/j.dam.2016.11.007","volume":"219","author":"J You","year":"2017","unstructured":"You, J., Wang, J., Cao, Y.: Approximate association via dissociation. Discret. Appl. Math. 219, 202\u2013209 (2017)","journal-title":"Discret. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-73879-2_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T10:22:29Z","timestamp":1672050149000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-73879-2_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030738785","9783030738792"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-73879-2_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"5 May 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Atlanta, GA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 May 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 May 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.gatech.edu\/ipco-2021\/","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":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"90","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":"33","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":"37% - 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":"15","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":"Due to the COVID-19 pandemic the conference took place virtually","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)"}}]}}