{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T14:05:00Z","timestamp":1761487500273},"publisher-location":"Berlin\/Heidelberg","reference-count":17,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354056764X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0029797","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T09:36:08Z","timestamp":1133429768000},"page":"63-73","source":"Crossref","is-referenced-by-count":6,"title":["On the worst-case behaviour of some approximation algorithms for the shortest common supersequence of k strings"],"prefix":"10.1007","author":[{"given":"Robert W.","family":"Irving","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Campbell B.","family":"Fraser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF01840365","volume":"2","author":"A. Apostolico","year":"1987","unstructured":"A. Apostolico and C. Guerra. The longest common subsequence problem revisited. Algorithmica, 2:315\u2013336, 1987.","journal-title":"Algorithmica"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. Unpublished manuscript, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"6_CR3","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(91)90094-X","volume":"38","author":"J.H. Bradford","year":"1991","unstructured":"J.H. Bradford and T.A. Jenkyns. On the inadequacy of tournament algorithms for the n-SCS problem. Information Processing Letters, 38:169\u2013171, 1991.","journal-title":"Information Processing Letters"},{"key":"6_CR4","first-page":"664","volume":"24","author":"D.S. Hirschberg","year":"1977","unstructured":"D.S. Hirschberg. Algorithms for the longest common subsequence problem. Journal of the A.C.M., 24:664\u2013675, 1977.","journal-title":"Journal of the A.C.M."},{"key":"6_CR5","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF01934514","volume":"24","author":"W.J. Hsu","year":"1984","unstructured":"W.J. Hsu and M.W. Du. Computing a longest common subsequence for a set of strings. BIT, 24:45\u201359, 1984.","journal-title":"BIT"},{"key":"6_CR6","first-page":"350","volume":"20","author":"J.W. Hunt","year":"1977","unstructured":"J.W. Hunt and T.G. Szymanski. A fast algorithm for computing longest common subsequences. Communications of the A.C.M., 20:350\u2013353, 1977.","journal-title":"Communications of the A.C.M."},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"R.W. Irving and C.B. Fraser. Two algorithms for the longest common subsequence of three (or more) strings. In Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, pages 214\u2013229. Springer-Verlag LNCS Vol. 644, 1992.","DOI":"10.1007\/3-540-56024-6_18"},{"key":"6_CR8","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/BF01934067","volume":"21","author":"S.Y. Itoga","year":"1981","unstructured":"S.Y. Itoga. The string merging problem. BIT, 21:20\u201330, 1981.","journal-title":"BIT"},{"key":"6_CR9","unstructured":"T. Jiang and M. Li. On the approximation of shortest common supersequences and longest common subsequences. Submitted for publication, 1992."},{"key":"6_CR10","first-page":"322","volume":"25","author":"D. Maier","year":"1978","unstructured":"D. Maier. The complexity of some problems on subsequences and supersequences. Journal of the A.C.M., 25:322\u2013336, 1978.","journal-title":"Journal of the A.C.M."},{"key":"6_CR11","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF01840446","volume":"1","author":"E.W. Myers","year":"1986","unstructured":"E.W. Myers. An O(ND) difference algorithm and its variations. Algorithmica, 1:251\u2013266, 1986.","journal-title":"Algorithmica"},{"key":"6_CR12","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF00264437","volume":"18","author":"N. Nakatsu","year":"1982","unstructured":"N. Nakatsu, Y. Kambayashi, and S. Yajima. A longest common subsequence algorithm suitable for similar text strings. Acta Informatica, 18:171\u2013179, 1982.","journal-title":"Acta Informatica"},{"key":"6_CR13","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"C.H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43:425\u2013440, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR14","first-page":"1","volume":"5","author":"V.G. Timkovskii","year":"1989","unstructured":"V.G. Timkovskii. Complexity of common subsequence and supersequence problems and related problems. English Translation from Kibernetika, 5:1\u201313, 1989.","journal-title":"Kibernetika"},{"key":"6_CR15","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","volume":"64","author":"E. Ukkonen","year":"1985","unstructured":"E. Ukkonen. Algorithms for approximate string matching. Information and Control, 64:100\u2013118, 1985.","journal-title":"Information and Control"},{"key":"6_CR16","first-page":"168","volume":"21","author":"R.A. Wagner","year":"1974","unstructured":"R.A. Wagner and M.J. Fischer. The string-to-string correction problem. Journal of the A.C.M., 21:168\u2013173, 1974.","journal-title":"Journal of the A.C.M."},{"key":"6_CR17","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0020-0190(90)90035-V","volume":"35","author":"S. Wu","year":"1990","unstructured":"S. Wu, U. Manber, G. Myers, and W. Miller. An O(NP) sequence comparison algorithm. Information Processing Letters, 35:317\u2013323, 1990.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0029797","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T08:34:09Z","timestamp":1586594049000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029797"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354056764X"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0029797","relation":{},"subject":[]}}