{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:33Z","timestamp":1760202633571,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642245824"},{"type":"electronic","value":"9783642245831"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-24583-1_6","type":"book-chapter","created":{"date-parts":[[2011,9,30]],"date-time":"2011-09-30T13:08:23Z","timestamp":1317388103000},"page":"44-54","source":"Crossref","is-referenced-by-count":1,"title":["Weighted Shortest Common Supersequence"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zvi","family":"Gotthilf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B. Riva","family":"Shalom","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2-3","key":"6_CR1","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/j.tcs.2008.01.006","volume":"395","author":"A. Amir","year":"2008","unstructured":"Amir, A., Chencinski, E., Iliopoulos, C.S., Kopelowitz, T., Zhang, H.: Property Matching and Weighted Matching. Theor. Comput. Sci.\u00a0395(2-3), 298\u2013310 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"6_CR2","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.jda.2010.02.001","volume":"8","author":"A. Amir","year":"2010","unstructured":"Amir, A., Gotthilf, Z., Shalom, R.: Weighted LCS. J. Discrete Algorithms\u00a08(3), 273\u2013281 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/11780441_33","volume-title":"Combinatorial Pattern Matching","author":"A. Amir","year":"2006","unstructured":"Amir, A., Iliopoulos, C.S., Kapah, O., Porat, E.: Approximate Matching in Weighted Sequences. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 365\u2013376. Springer, Heidelberg (2006)"},{"issue":"1","key":"6_CR4","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":"6_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/978-3-642-21458-5_39","volume-title":"Combinatorial Pattern Matching","author":"R. Clifford","year":"2011","unstructured":"Clifford, R., Gotthilf, Z., Lewenstein, M., Popa, A.: Restricted common superstring and restricted common supersequence. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 467\u2013478. Springer, Heidelberg (to appear, 2011)"},{"key":"6_CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. 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., New York (1979)"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/978-3-642-03784-9_27","volume-title":"String Processing and Information Retrieval","author":"Z. Gotthilf","year":"2009","unstructured":"Gotthilf, Z., Lewenstein, M.: Improved Approximation Results on the Shortest Common Supersequence Problem. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 277\u2013284. Springer, Heidelberg (2009)"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Iliopoulos, C., Makris, C., Panagis, Y., Perdikuri, K., Theodoridis, E., Tsakalidis, A.K.: Efficient Algorithms for Handling Molecular Weighted Sequences. In: IFIP TCS, pp. 265\u2013278 (2004)","DOI":"10.1007\/1-4020-8141-3_22"},{"key":"6_CR9","unstructured":"Iliopoulos, C.S., Mouchard, L., Pedikuri, K., Tsakalidis, A.K.: Computing the repetitions in a weighted sequence. In: Proc. of the 2003 Prague Stringology Conference (PSC 2003), vol.\u00a010, pp. 91\u201398 (2003)"},{"issue":"5","key":"6_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(5), 1122\u20131139 (1995)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"6_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(2), 322\u2013336 (1978)","journal-title":"Journal of the ACM"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","volume":"22","author":"J.D. Thompson","year":"1994","unstructured":"Thompson, J.D., Higgins, D.G., Gibson, T.J.: CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res.\u00a022, 4673\u20134680 (1994)","journal-title":"Nucleic Acids Res."},{"issue":"2","key":"6_CR13","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0304-3975(81)90075-X","volume":"16","author":"K.-J. R\u00e4ih\u00e4","year":"1981","unstructured":"R\u00e4ih\u00e4, K.-J., Ukkonen, E.: The Shortest Common Supersequence Problem over Binary Alphabet is NP-complete. Theoretical Computer Science\u00a016(2), 187\u2013198 (1981)","journal-title":"Theoretical Computer Science"},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1137\/0128004","volume":"28","author":"D. Sankoff","year":"1975","unstructured":"Sankoff, D.: Minimal Mutation Trees of Sequences. SIAM Journal on Applied Mathematics\u00a028, 35\u201342 (1975)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"6_CR15","first-page":"565","volume":"25","author":"V.G. Timkovsky","year":"1989","unstructured":"Timkovsky, V.G.: Complexity of common subsequence and supersequence problems and related problems. Kibernetika\u00a025, 565\u2013580 (1989); English Translation in Cybernetics 25: 565-580, 1990","journal-title":"Kibernetika"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"1304","DOI":"10.1126\/science.1058040","volume":"291","author":"J.C. Venter","year":"2001","unstructured":"Venter, J.C., Celera Genomics Corporation: The Sequence of the Human Genome. Science\u00a0291, 1304\u20131351 (2001)","journal-title":"Science"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-24583-1_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T08:07:38Z","timestamp":1554710858000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-24583-1_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642245824","9783642245831"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-24583-1_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}