{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T18:10:10Z","timestamp":1746295810132,"version":"3.40.4"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319087825"},{"type":"electronic","value":"9783319087832"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08783-2_13","type":"book-chapter","created":{"date-parts":[[2014,7,5]],"date-time":"2014-07-05T14:04:30Z","timestamp":1404569070000},"page":"141-153","source":"Crossref","is-referenced-by-count":0,"title":["On the Kernelization Complexity of String Problems"],"prefix":"10.1007","author":[{"given":"Manu","family":"Basavaraju","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashutosh","family":"Rai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Andoni, A., Indyk, P., Patrascu, M.: On the optimality of the dimensionality reduction method. In: FOCS, pp. 449\u2013458 (2006)","DOI":"10.1109\/FOCS.2006.56"},{"issue":"8","key":"13_CR2","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci.\u00a075(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR3","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: A new technique for kernelization lower bounds. In: STACS, pp. 165\u2013176 (2011)"},{"issue":"35","key":"13_CR4","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci.\u00a0412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Boucher, C., Ma, B.: Closest string with outliers. BMC Bioinformatics\u00a012(S-1), S55 (2011)","DOI":"10.1186\/1471-2105-12-S1-S55"},{"issue":"2","key":"13_CR6","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1089\/10665270252935430","volume":"9","author":"J. Buhler","year":"2002","unstructured":"Buhler, J., Tompa, M.: Finding motifs using random projections. Journal of Computational Biology\u00a09(2), 225\u2013242 (2002)","journal-title":"Journal of Computational Biology"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: STOC, pp. 251\u2013260 (2010)","DOI":"10.1145\/1806689.1806725"},{"key":"13_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"Automata, Languages and Programming","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and ids. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 378\u2013389. Springer, Heidelberg (2009)"},{"key":"13_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/3-540-45841-7_21","volume-title":"STACS 2002","author":"M.R. Fellows","year":"2002","unstructured":"Fellows, M.R., Gramm, J., Niedermeier, R.: On the parameterized intractability of CLOSEST SUBSTRING and related problems. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 262\u2013273. Springer, Heidelberg (2002)"},{"issue":"2","key":"13_CR10","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s00493-006-0011-4","volume":"26","author":"M.R. Fellows","year":"2006","unstructured":"Fellows, M.R., Gramm, J., Niedermeier, R.: On the parameterized intractability of motif search problems. Combinatorica\u00a026(2), 141\u2013167 (2006)","journal-title":"Combinatorica"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: STOC, pp. 133\u2013142 (2008)","DOI":"10.1145\/1374376.1374398"},{"issue":"2","key":"13_CR12","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF02679443","volume":"30","author":"M. Frances","year":"1997","unstructured":"Frances, M., Litman, A.: On covering problems of codes. Theory Comput. Syst.\u00a030(2), 113\u2013119 (1997)","journal-title":"Theory Comput. Syst."},{"key":"13_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/3-540-45678-3_38","volume-title":"Algorithms and Computation","author":"J. Gramm","year":"2001","unstructured":"Gramm, J., Niedermeier, R., Rossmanith, P.: Exact solutions for closest string and related problems. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol.\u00a02223, pp. 441\u2013453. Springer, Heidelberg (2001)"},{"issue":"1","key":"13_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0890-5401(03)00057-9","volume":"185","author":"J.K. Lanctot","year":"2003","unstructured":"Lanctot, J.K., Li, M., Ma, B., Wang, S., Zhang, L.: Distinguishing string selection problems. Inf. Comput.\u00a0185(1), 41\u201355 (2003)","journal-title":"Inf. Comput."},{"issue":"1","key":"13_CR15","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jcss.2002.1823","volume":"65","author":"M. Li","year":"2002","unstructured":"Li, M., Ma, B., Wang, L.: Finding similar regions in many sequences. J. Comput. Syst. Sci.\u00a065(1), 73\u201396 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"13_CR16","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1145\/506147.506150","volume":"49","author":"M. Li","year":"2002","unstructured":"Li, M., Ma, B., Wang, L.: On the closest string and substring problems. J. ACM\u00a049(2), 157\u2013171 (2002)","journal-title":"J. ACM"},{"key":"13_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/3-540-45123-4_10","volume-title":"Combinatorial Pattern Matching","author":"B. Ma","year":"2000","unstructured":"Ma, B.: A polynominal time approximation scheme for the closest substring problem. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol.\u00a01848, pp. 99\u2013107. Springer, Heidelberg (2000)"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Marx, D.: The closest substring problem with small distances. In: FOCS, pp. 63\u201372 (2005)","DOI":"10.1109\/SFCS.2005.70"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Pevzner, P.A.: Computational molecular biology - an algorithmic approach. MIT Press (2000)","DOI":"10.7551\/mitpress\/2022.001.0001"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08783-2_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T17:49:08Z","timestamp":1746294548000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08783-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319087825","9783319087832"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08783-2_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}