{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T05:42:06Z","timestamp":1742967726400,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642112683"},{"type":"electronic","value":"9783642112690"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-11269-0_22","type":"book-chapter","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T08:36:15Z","timestamp":1259656575000},"page":"264-275","source":"Crossref","is-referenced-by-count":18,"title":["Two Edge Modification Problems without Polynomial Kernels"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Kratsch","sequence":"first","affiliation":[]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N.: Kernelization algorithms for d-hitting set problems. In: Dehne, et al. (eds.) [8], pp. 434\u2013445","DOI":"10.1007\/978-3-540-73951-7_38"},{"key":"22_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11847250","volume-title":"Parameterized and Exact Computation","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L., Cai, L., Chen, J., Fellows, M.R., Telle, J.A., Marx, D.: IWPEC 2006. LNCS, vol.\u00a04169. Springer, Heidelberg (2006)"},{"key":"22_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/978-3-540-70575-8_46","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels (extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 563\u2013574. Springer, Heidelberg (2008)"},{"key":"22_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/978-3-642-04128-0_57","volume-title":"ESA 2009","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 635\u2013646. Springer, Heidelberg (2009)"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.endm.2009.02.008","volume":"32","author":"D. Br\u00fcgmann","year":"2009","unstructured":"Br\u00fcgmann, D., Komusiewicz, C., Moser, H.: On generating triangle-free graphs. Electronic Notes in Discrete Mathematics\u00a032, 51\u201358 (2009)","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"13","key":"22_CR6","doi-asserted-by":"publisher","first-page":"1824","DOI":"10.1016\/j.dam.2006.03.031","volume":"154","author":"P. Burzyn","year":"2006","unstructured":"Burzyn, P., Bonomo, F., Dur\u00e1n, G.: NP-completeness results for edge modification problems. Discrete Applied Mathematics\u00a0154(13), 1824\u20131844 (2006)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"22_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. Information Processing Letters\u00a058(4), 171\u2013176 (1996)","journal-title":"Information Processing Letters"},{"key":"22_CR8","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms and Data Structures","year":"2007","unstructured":"Dehne, F., Sack, J.-R., Zeh, N. (eds.): WADS 2007. LNCS, vol.\u00a04619. Springer, Heidelberg (2007)"},{"key":"22_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/11672142_29","volume-title":"STACS 2006","author":"J. D\u00edaz","year":"2006","unstructured":"D\u00edaz, J., Thilikos, D.M.: Fast fpt-algorithms for cleaning grids. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 361\u2013371. Springer, Heidelberg (2006)"},{"key":"22_CR10","series-title":"Monographs in Computer Science","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1998","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, Heidelberg (1998)"},{"key":"22_CR11","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2006)"},{"key":"22_CR12","first-page":"133","volume-title":"STOC","author":"L. Fortnow","year":"2008","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: STOC, pp. 133\u2013142. ACM, New York (2008)"},{"key":"22_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1007\/978-3-540-77120-3_79","volume-title":"Algorithms and Computation","author":"J. Guo","year":"2007","unstructured":"Guo, J.: Problem kernels for NP-complete edge deletion problems: Split and related graphs. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 915\u2013926. Springer, Heidelberg (2007)"},{"issue":"8-10","key":"22_CR14","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1016\/j.tcs.2008.10.021","volume":"410","author":"J. Guo","year":"2009","unstructured":"Guo, J.: A more effective linear kernelization for cluster editing. Theoretical Computer Science\u00a0410(8-10), 718\u2013726 (2009)","journal-title":"Theoretical Computer Science"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Guo, J., Uhlmann, J.: Kernelization and complexity results for connectivity augmentation problems. In: Dehne, et al [8], pp. 483\u2013494","DOI":"10.1007\/978-3-540-73951-7_42"},{"issue":"6","key":"22_CR16","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S. Khanna","year":"2000","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.P.: The approximability of constraint satisfaction problems. SIAM Journal on Computing.\u00a030(6), 1863\u20131920 (2000)","journal-title":"SIAM Journal on Computing."},{"issue":"1","key":"22_CR17","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. Discrete Applied Mathematics\u00a0113(1), 109\u2013128 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"22_CR18","doi-asserted-by":"crossref","unstructured":"Rose, D.J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Graph Theory and Computing, pp. 183\u2013217 (1972)","DOI":"10.1016\/B978-1-4832-3187-7.50018-0"},{"issue":"14","key":"22_CR19","doi-asserted-by":"publisher","first-page":"1787","DOI":"10.1093\/bioinformatics\/btg232","volume":"19","author":"R. Sharan","year":"2003","unstructured":"Sharan, R., Maron-Katz, A., Shamir, R.: CLICK and EXPANDER: a system for clustering and visualizing gene expression data. Bioinformatics\u00a019(14), 1787\u20131799 (2003)","journal-title":"Bioinformatics"},{"key":"22_CR20","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C.-K. Yap","year":"1983","unstructured":"Yap, C.-K.: Some consequences of non-uniform conditions on uniform classes. Theoretical Computer Science\u00a026, 287\u2013300 (1983)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11269-0_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,30]],"date-time":"2023-01-30T13:34:36Z","timestamp":1675085676000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-11269-0_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642112683","9783642112690"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11269-0_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}