{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:21:36Z","timestamp":1725571296652},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175138"},{"type":"electronic","value":"9783642175145"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17514-5_16","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T15:09:23Z","timestamp":1291388963000},"page":"180-191","source":"Crossref","is-referenced-by-count":1,"title":["Approximability of Constrained LCS"],"prefix":"10.1007","author":[{"given":"Minghui","family":"Jiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_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: Proceedings of the 2009 International Conference on Bioinformatics & Computational Biology (BIOCOMP 2009), pp. 646\u2013649 (2009)"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1142\/S0129054105003674","volume":"16","author":"A. Arslan","year":"2005","unstructured":"Arslan, A., E\u011fecio\u011flu, \u00d6.: Algorithms for the constrained longest common subsequence problems. International Journal of Foundations of Computer Science\u00a016, 1099\u20131109 (2005)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1016\/j.ipl.2010.07.015","volume":"110","author":"P. Bonizzoni","year":"2010","unstructured":"Bonizzoni, P., Della Vedova, G., Dondi, R., Pirola, Y.: Variants of constrained longest common subsequence. Information Processing Letters\u00a0110, 877\u2013881 (2010)","journal-title":"Information Processing Letters"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Chen, Y.-C., Chao, K.-M.: On the generalized constrained longest common subsequence problems. Journal of Combinatorial Optimization, doi:10.1007\/s10878-009-9262-5.","DOI":"10.1007\/s10878-009-9262-5"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/j.ipl.2004.02.008","volume":"90","author":"F.Y.L. Chin","year":"2004","unstructured":"Chin, F.Y.L., De Santis, A., Ferrara, A.L., Ho, N.L., Kim, S.K.: L Ho, and S. K. Kim. A simple algorithm for the constrained sequence problems. Information Processing Letters\u00a090, 175\u2013179 (2004)","journal-title":"Information Processing Letters"},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/978-3-540-69068-9_24","volume-title":"Combinatorial Pattern Matching","author":"Z. Gotthilf","year":"2008","unstructured":"Gotthilf, Z., Hermelin, D., Lewenstein, M.: Constrained LCS: hardness and approximation. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol.\u00a05029, pp. 255\u2013262. Springer, Heidelberg (2008)"},{"key":"16_CR7","unstructured":"Halld\u00f3rsson, M.M.: Approximation via partitioning. Technical Report IS-RR-95-0003F, School of Information Science, Japan Advanced Institute of Science and Technology, Hokuriku (1995)"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n\n                  1\u2009\u2212\u2009\u03b5\n                  . Acta Mathematica\u00a0182, 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.ipl.2007.09.008","volume":"106","author":"C.S. Iliopoulos","year":"2008","unstructured":"Iliopoulos, C.S., Rahman, M.S.: New efficient algorithms for the LCS and constrained LCS problems. Information Processing Letters\u00a0106, 13\u201318 (2008)","journal-title":"Information Processing Letters"},{"key":"16_CR10","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":"16_CR11","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, 322\u2013336 (1978)","journal-title":"Journal of the ACM"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(95)00014-N","volume":"145","author":"M. Middendorf","year":"1995","unstructured":"Middendorf, M.: On finding minimal, maximal, and consistent sequences over a binary alphabet. Theoretical Computer Science\u00a0145, 317\u2013327 (1995)","journal-title":"Theoretical Computer Science"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/j.tcs.2004.02.001","volume":"320","author":"M. Middendorf","year":"2004","unstructured":"Middendorf, M., Manlove, D.F.: Combined super-\/substring and super-\/subsequence problems. Theoretical Computer Science\u00a0320, 247\u2013267 (2004)","journal-title":"Theoretical Computer Science"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.ipl.2003.07.001","volume":"88","author":"Y.-T. Tsai","year":"2003","unstructured":"Tsai, Y.-T.: The constrained longest common subsequence problem. Information Processing Letters\u00a088, 173\u2013176 (2003)","journal-title":"Information Processing Letters"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D. Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of Max Clique and Chromatic Number. Theory of Computing\u00a03, 103\u2013128 (2007)","journal-title":"Theory of Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17514-5_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,22]],"date-time":"2019-03-22T13:06:49Z","timestamp":1553260009000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17514-5_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175138","9783642175145"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17514-5_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}