{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T23:58:26Z","timestamp":1777420706878,"version":"3.51.4"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,13]],"date-time":"2022-01-13T00:00:00Z","timestamp":1642032000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,13]],"date-time":"2022-01-13T00:00:00Z","timestamp":1642032000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["281\/17"],"award-info":[{"award-number":["281\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"crossref","award":["G-1347-304.6\/2016"],"award-info":[{"award-number":["G-1347-304.6\/2016"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s00453-021-00899-4","type":"journal-article","created":{"date-parts":[[2022,1,13]],"date-time":"2022-01-13T00:03:47Z","timestamp":1642032227000},"page":"464-481","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Additive Approximation of Generalized Tur\u00e1n Questions"],"prefix":"10.1007","volume":"84","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0587-7181","authenticated-orcid":false,"given":"Clara","family":"Shikhelman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,13]]},"reference":[{"key":"899_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Shapira, A., Sudakov, B.: Additive approximation for edge-deletion problems. Ann. Math. 170, 371\u2013411 (2009)","DOI":"10.4007\/annals.2009.170.371"},{"issue":"1","key":"899_CR2","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1137\/070695952","volume":"23","author":"N Alon","year":"2009","unstructured":"Alon, N., Shapira, A., Stav, U.: Can a graph have distinct regular partitions? SIAM J. Discret. Math. 23(1), 278\u2013287 (2009)","journal-title":"SIAM J. Discret. Math."},{"key":"899_CR3","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/j.jctb.2016.03.004","volume":"121","author":"N Alon","year":"2016","unstructured":"Alon, N., Shikhelman, C.: Many T copies in H-free graphs. J. Comb. Theor. Ser B 121, 146\u2013172 (2016)","journal-title":"J. Comb. Theor. Ser B"},{"key":"899_CR4","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0216024","volume":"16","author":"T Asano","year":"1987","unstructured":"Asano, T.: An application of duality to edge-deletion problems. SIAM J. Comput. 16, 312\u2013331 (1987)","journal-title":"SIAM J. Comput."},{"key":"899_CR5","doi-asserted-by":"crossref","unstructured":"Asano, T., Hirata, T.: Edge-deletion and edge-contraction problems. In: Proceedings of the fourteenth annual ACM symposium on Theory of computing, 245-254 1982","DOI":"10.1145\/800070.802198"},{"key":"899_CR6","doi-asserted-by":"crossref","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation clustering, Proc. of the 43rd IEEE FOCS , 238-247 2002","DOI":"10.1109\/SFCS.2002.1181947"},{"issue":"4","key":"899_CR7","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":"899_CR8","doi-asserted-by":"crossref","unstructured":"Cirino, K., Muthukrishnan, S., Narayanaswamy, N., Ramesh, H.: graph editing to bipartite interval graphs: exact and asymptotic bounds. In: International Conference on Foundations of Software Technology and Theoretical Computer Science, 37-53 1997","DOI":"10.1007\/BFb0058021"},{"issue":"3","key":"899_CR9","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1137\/S0097539793247634","volume":"24","author":"RA Duke","year":"1995","unstructured":"Duke, R.A., Lefmann, H., R\u00f6dl, V.: A fast approximation algorithm for computing the frequencies of subgraphs in a given graph. SIAM J. Comput. 24(3), 598\u2013620 (1995)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"899_CR10","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"issue":"3","key":"899_CR11","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1109\/31.1748","volume":"35","author":"ES El-Mallah","year":"1988","unstructured":"El-Mallah, E.S., Colbourn, C.J.: The complexity of some edge deletion problems. IEEE Trans. Circuits Syst. 35(3), 354\u2013362 (1988)","journal-title":"IEEE Trans. Circuits Syst."},{"issue":"2","key":"899_CR12","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1002\/rsa.10017","volume":"20","author":"P Frankl","year":"2002","unstructured":"Frankl, P., R\u00f6dl, V.: Extremal problems on set systems. Random Struct. Algorithms 20(2), 131\u2013164 (2002)","journal-title":"Random Struct. Algorithms"},{"key":"899_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., San Francisco (1979)"},{"key":"899_CR14","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"PW Goldberg","year":"1995","unstructured":"Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Biol. 2, 139\u2013152 (1995)","journal-title":"J. Comput. Biol."},{"key":"899_CR15","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1006\/aama.1994.1009","volume":"15","author":"MC Golumbic","year":"1994","unstructured":"Golumbic, M.C., Kaplan, H., Shamir, R.: On the complexity of DNA physical mapping. Adv. Appl. Math. 15, 251\u2013261 (1994)","journal-title":"Adv. Appl. Math."},{"issue":"2","key":"899_CR16","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci. 289(2), 997\u20131008 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"899_CR17","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/3-540-45878-6_3","volume":"2292","author":"J Koml\u00f3s","year":"2002","unstructured":"Koml\u00f3s, J., Shokoufandeh, A., Simonovits, M., Szemer\u00e9di, E.: The regularity lemma and its applications in graph theory. Theor. Asp. Comput. Sci. 2292, 84\u2013112 (2002)","journal-title":"Theor. Asp. Comput. Sci."},{"key":"899_CR18","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0166-218X(00)00391-7","volume":"113","author":"A Natanzon","year":"2001","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discret. Appl. Math. 113, 109\u2013128 (2001)","journal-title":"Discret. Appl. Math."},{"issue":"6","key":"899_CR19","doi-asserted-by":"publisher","first-page":"887","DOI":"10.1017\/S0963548307008565","volume":"16","author":"V R\u00f6dl","year":"2007","unstructured":"R\u00f6dl, V., Schacht, M.: Regular partitions of hypergraphs: counting lemmas. Comb. Probab. Comput. 16(6), 887\u2013901 (2007)","journal-title":"Comb. Probab. Comput."},{"key":"899_CR20","unstructured":"Szemer\u00e9di, E.: Regular partitions of graphs, Colloques Internationaux C.N.R.S. No 260 - Probl\u00e9mes Combinatoires et Th\u00e9orie des Graphes, Orsay (1976)"},{"key":"899_CR21","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"WT Tutte","year":"1954","unstructured":"Tutte, W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6, 347\u2013352 (1954)","journal-title":"Can. J. Math."},{"key":"899_CR22","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1137\/0210021","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10, 297\u2013309 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00899-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00899-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00899-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T05:17:08Z","timestamp":1726463828000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00899-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,13]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["899"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00899-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,13]]},"assertion":[{"value":"11 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}