{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:22:51Z","timestamp":1777965771929,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642037832","type":"print"},{"value":"9783642037849","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-03784-9_27","type":"book-chapter","created":{"date-parts":[[2009,8,21]],"date-time":"2009-08-21T14:47:42Z","timestamp":1250866062000},"page":"277-284","source":"Crossref","is-referenced-by-count":4,"title":["Improved Approximation Results on the Shortest Common Supersequence Problem"],"prefix":"10.1007","author":[{"given":"Zvi","family":"Gotthilf","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-2","key":"27_CR1","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0304-3975(97)00023-6","volume":"182","author":"V. Bafna","year":"1997","unstructured":"Bafna, V., Lawler, E.L., Pevzner, P.A.: Approximation Algorithms for Multiple Sequence Alignment. Theoretical Computer Science\u00a0182(1-2), 233\u2013244 (1997)","journal-title":"Theoretical Computer Science"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Barone, P., Bonizzoni, P., Vedova, G.D., Mauri, G.: An approximation algorithm for the shortest common supersequence problem: an experimental analysis. In: ACM Symposium on Applied Computing, pp. 56\u201360 (2001)","DOI":"10.1145\/372202.372275"},{"key":"27_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/11494669_7","volume-title":"Computational Intelligence and Bioinspired Systems","author":"C. Cotta","year":"2005","unstructured":"Cotta, C.: A Comparison of Evolutionary Approaches to the Shortest Common Supersequence Problem. In: Cabestany, J., Prieto, A.G., Sandoval, F. (eds.) IWANN 2005. LNCS, vol.\u00a03512, pp. 50\u201358. Springer, Heidelberg (2005)"},{"key":"27_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/11499305_9","volume-title":"Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach","author":"C. Cotta","year":"2005","unstructured":"Cotta, C.: Memetic Algorithms with Partial Lamarckism for the Shortest Common Supersequence Problem. In: Mira, J., \u00c1lvarez, J.R. (eds.) IWINAC 2005. LNCS, vol.\u00a03562, pp. 84\u201391. Springer, Heidelberg (2005)"},{"issue":"2","key":"27_CR5","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G. Even","year":"1998","unstructured":"Even, G., Naor, J., Schieber, B., Sudan, M.: Approximating Minimum Feedback Sets and Multicuts in Directed Graphs. Algorithmica\u00a020(2), 151\u2013174 (1998)","journal-title":"Algorithmica"},{"issue":"3","key":"27_CR6","first-page":"303","volume":"2","author":"C.B. Fraser","year":"1995","unstructured":"Fraser, C.B., Irving, R.W.: Approximation Algorithms for the Shortest Common Supersequence. Nordic Journal of Computing\u00a02(3), 303\u2013325 (1995)","journal-title":"Nordic Journal of Computing"},{"issue":"5","key":"27_CR7","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":"27_CR8","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"},{"issue":"2","key":"27_CR9","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0304-3975(93)90200-D","volume":"108","author":"M. Middendorf","year":"1993","unstructured":"Middendorf, M.: The Shortest Common Nonsubsequence Problem is NP-Complete. Theoretical Computer Science\u00a0108(2), 365\u2013369 (1993)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"27_CR10","doi-asserted-by":"publisher","first-page":"1763","DOI":"10.1137\/0152101","volume":"52","author":"P.A. Pevzner","year":"1992","unstructured":"Pevzner, P.A.: Multiple Alignment, Communication Cost, and Graph Matching. SIAM Journal on Applied Mathematics\u00a052(6), 1763\u20131779 (1992)","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"4","key":"27_CR11","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. Journal of Computer and System Sciences\u00a067(4), 757\u2013771 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR12","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, 187\u2013198 (1981)","journal-title":"Theoretical Computer Science"},{"key":"27_CR13","volume-title":"Combinatorial Algorithms","author":"E.M. Reingold","year":"1977","unstructured":"Reingold, E.M., Nievergelt, J., Deo, N.: Combinatorial Algorithms. Prentice-Hall Inc., Englewood Cliffs (1977)"},{"issue":"3","key":"27_CR14","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/S0895480192234277","volume":"11","author":"A.R. Rubinov","year":"1998","unstructured":"Rubinov, A.R., Timkovsky, V.G.: String Noninclusion Optimization Problems. SIAM Journal on Discrete Mathematics\u00a011(3), 456\u2013467 (1998)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"27_CR15","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":"27_CR16","first-page":"1","volume":"5","author":"V.G. Timkovsky","year":"1989","unstructured":"Timkovsky, V.G.: Complexity of common subsequence and supersequence problems and related problems. Kibernetika\u00a05, 1\u201313 (1989); English Translation in Cybernetics 25, 565\u2013580 (1990)","journal-title":"Kibernetika"},{"key":"27_CR17","series-title":"Lecture Notes in Computer Science","first-page":"258","volume-title":"String Processing and Information Retrieval","author":"V.G. Timkovsky","year":"2008","unstructured":"Timkovsky, V.G.: Some Approximations for Shortest Common Nonsubsequences and Supersequences. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol.\u00a05280, pp. 258\u2013269. Springer, Heidelberg (2008)"}],"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-03784-9_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,9]],"date-time":"2019-03-09T13:31:01Z","timestamp":1552138261000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03784-9_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642037832","9783642037849"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03784-9_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}