{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:33:31Z","timestamp":1759638811579,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642312649"},{"type":"electronic","value":"9783642312656"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31265-6_11","type":"book-chapter","created":{"date-parts":[[2012,6,12]],"date-time":"2012-06-12T03:28:23Z","timestamp":1339471703000},"page":"138-148","source":"Crossref","is-referenced-by-count":4,"title":["Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths"],"prefix":"10.1007","author":[{"given":"Guillaume","family":"Blin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurent","family":"Bulteau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minghui","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pedro J.","family":"Tejada","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","unstructured":"Ann, H.-Y., Yang, C.-B., Tseng, C.-T., Hor, C.-Y.: Fast algorithms for computing the constrained lcs of run-length encoded strings. In: Arabnia, H.R., Yang, M.Q. (eds.) Proc. International Conference on Bioinformatics & Computational Biology (BIOCOMP), Las Vegas, USA, pp. 646\u2013649. CSREA Press (2009)"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.ipl.2008.07.005","volume":"108","author":"H.-Y. Ann","year":"2008","unstructured":"Ann, H.-Y., Yang, C.-B., Tseng, C.-T., Hor, C.-Y.: A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings. Information Processing Letters\u00a0108, 360\u2013364 (2008)","journal-title":"Information Processing Letters"},{"issue":"1","key":"11_CR3","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1006\/jcom.1998.0493","volume":"15","author":"A. Apostolico","year":"1999","unstructured":"Apostolico, A., Landau, G.M., Skiena, S.: Matching for run-length encoded strings. Journal of Complexity\u00a015(1), 4\u201316 (1999)","journal-title":"Journal of Complexity"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Bergroth, L., Hakonen, H., Raita, T.: A survey of longest common subsequence algorithms. In: Proc. of the 7th International Symposium on String Processing Information Retrieval (SPIRE), Coru $\\tilde{\\text{n}}$ a, Spain, pp. 39\u201348. IEEE Computer Society (2000)","DOI":"10.1109\/SPIRE.2000.878178"},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P. Berman","year":"1992","unstructured":"Berman, P., Schnitger, G.: On the complexity of approximating the independent set problem. Information and Computation\u00a096, 77\u201394 (1992)","journal-title":"Information and Computation"},{"issue":"1","key":"11_CR6","first-page":"49","volume":"11","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hallett, M.T., Wareham, H.T.: Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences\u00a011(1), 49\u201357 (1995)","journal-title":"Computer Applications in the Biosciences"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(94)00251-D","volume":"147","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Wareham, H.T.: The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science\u00a0147, 31\u201354 (1994)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"11_CR8","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0166-218X(00)00300-0","volume":"110","author":"P. Bonizzoni","year":"2001","unstructured":"Bonizzoni, P., Della Vedova, G., Mauri, G.: Experimenting an approximation algorithm for the lcs. Discrete Applied Mathematics\u00a0110(1), 13\u201324 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0020-0190(95)00005-W","volume":"54","author":"H. Bunke","year":"1995","unstructured":"Bunke, H., Csirik, J.: An improved algorithm for computing the edit distance of run-length coded strings. Information Processing Letters\u00a054, 93\u201396 (1995)","journal-title":"Information Processing Letters"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings, Cambridge (2007)","DOI":"10.1017\/CBO9780511546853"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.ipl.2004.02.011","volume":"90","author":"V. Freschi","year":"2004","unstructured":"Freschi, V., Bogliolo, A.: Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism. Information Processing Letters\u00a090, 167\u2013173 (2004)","journal-title":"Information Processing Letters"},{"key":"11_CR12","unstructured":"Halld\u00f3rsson, M.M.: Approximation via partitioning. Technical report, School of Information Science, Japan Advanced Institute of Science and Technology, Hokuriku (1995)"},{"key":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1007\/978-3-642-10631-6_109","volume-title":"Algorithms and Computation","author":"P.-H. Hsu","year":"2009","unstructured":"Hsu, P.-H., Chen, K.-Y., Chao, K.-M.: Finding All Approximate Gapped Palindromes. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 1084\u20131093. Springer, Heidelberg (2009)"},{"key":"11_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-540-69733-6_32","volume-title":"Computing and Combinatorics","author":"G.S. Huang","year":"2008","unstructured":"Huang, G.S., Liu, J.J., Wang, Y.L.: Sequence Alignment Algorithms for Run-Length-Encoded Strings. In: Hu, X., Wang, J. (eds.) COCOON 2008. LNCS, vol.\u00a05092, pp. 319\u2013330. Springer, Heidelberg (2008)"},{"key":"11_CR15","doi-asserted-by":"publisher","first-page":"1122","DOI":"10.1137\/S009753979223842X","volume":"24","author":"T. Jiang","year":"1995","unstructured":"Jiang, T., Li, M.: On the approximation of shortest common supersequences and longest common subsequences. SIAM Journal on Computing\u00a024, 1122\u20131139 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"11_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1007\/978-3-642-10631-6_109","volume-title":"Algorithms and Computation","author":"P.-H. Hsu","year":"2009","unstructured":"Hsu, P.-H., Chen, K.-Y., Chao, K.-M.: Finding All Approximate Gapped Palindromes. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 1084\u20131093. Springer, Heidelberg (2009)"},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1016\/j.tcs.2008.01.008","volume":"395","author":"J.W. Kim","year":"2008","unstructured":"Kim, J.W., Amir, A., Landau, G.M., Park, K.: Computing similarity of run-length encoded strings with affine gap penalty. Theoretical Computer Science\u00a0395, 268\u2013282 (2008)","journal-title":"Theoretical Computer Science"},{"key":"11_CR18","doi-asserted-by":"publisher","first-page":"3942","DOI":"10.1016\/j.tcs.2009.05.032","volume":"410","author":"J.J. Liu","year":"2009","unstructured":"Liu, J.J., Huang, G.S., Wang, Y.L.: A fast algorithm for finding the positions of all squares in a run-length encoded string. Theoretical Computer Science\u00a0410, 3942\u20133948 (2009)","journal-title":"Theoretical Computer Science"},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.ipl.2007.07.006","volume":"105","author":"J.J. Liu","year":"2007","unstructured":"Liu, J.J., Huang, G.S., Wang, Y.L., Lee, R.C.T.: Edit distance for a run-length-encoded string and an uncompressed string. Information Processing Letters\u00a0105, 12\u201316 (2007)","journal-title":"Information Processing Letters"},{"key":"11_CR20","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.jco.2007.06.003","volume":"24","author":"J.J. Liu","year":"2008","unstructured":"Liu, J.J., Wang, Y.L., Lee, R.C.T.: Finding a longest common subsequence between a run-length-encoded string and an uncompressed string. Journal of Complexity\u00a024, 173\u2013184 (2008)","journal-title":"Journal of Complexity"},{"issue":"2","key":"11_CR21","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. Journal of the ACM\u00a025(2), 322\u2013336 (1978)","journal-title":"Journal of the ACM"},{"key":"11_CR22","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1016\/j.tcs.2008.12.016","volume":"410","author":"W. Matsubara","year":"2009","unstructured":"Matsubara, W., Inenaga, S., Ishino, A., Shinohara, A., Nakamura, T., Hashimoto, K.: Efficient algorithms to compute compressed longest common substrings and compressed palindromes. Theoretical Computer Science\u00a0410, 900\u2013913 (2009)","journal-title":"Theoretical Computer Science"},{"key":"11_CR23","unstructured":"Mitchell, J.S.B.: A geometric shortest path problem, with application to computing a longest common subsequence in run-length encoded strings. Technical report, Department of Applied Mathematics, SUNY Stony Brook (1997)"},{"issue":"4","key":"11_CR24","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K. Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. of Computer and System Sciences\u00a067(4), 757\u2013771 (2003); Special issue on Parameterized computation and complexity","journal-title":"J. of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31265-6_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T22:43:06Z","timestamp":1743374586000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31265-6_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642312649","9783642312656"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31265-6_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}