{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:11:13Z","timestamp":1725664273297},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540580942"},{"type":"electronic","value":"9783540484509"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58094-8_16","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:11:56Z","timestamp":1330269116000},"page":"173-183","source":"Crossref","is-referenced-by-count":2,"title":["Maximal common subsequences and minimal common supersequences"],"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","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"16_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":"16_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proc. 33rd IEEE Symp. Found. Comp. Sci., pages 14\u201323, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"16_CR3","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability. Freeman, San Francisco, CA., 1979."},{"key":"16_CR4","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"M.M. Halld\u00f3rsson","year":"1993","unstructured":"M.M. Halld\u00f3rsson. Approximating the minimum maximal independence number. Information Processing Letters, 46:169\u2013172, 1993.","journal-title":"Information Processing Letters"},{"key":"16_CR5","first-page":"341","volume":"18","author":"D.S. Hirschberg","year":"1975","unstructured":"D.S. Hirschberg. A linear space algorithm for computing maximal common subsequences. Communications of the A.C.M., 18:341\u2013343, 1975.","journal-title":"Communications of the A.C.M."},{"key":"16_CR6","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":"16_CR7","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":"16_CR8","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0020-0190(91)90188-N","volume":"37","author":"R.W. Irving","year":"1991","unstructured":"R.W. Irving. On approximating the minimum independent dominating set. Information Processing Letters, 37:197\u2013200, 1991.","journal-title":"Information Processing Letters"},{"key":"16_CR9","unstructured":"T. Jiang and M. Li. On the approximation of shortest common supersequences and longest common subsequences. Submitted for publication, 1992."},{"key":"16_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":"16_CR11","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":"16_CR12","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0304-3975(81)90075-X","volume":"16","author":"K-J. Raiha","year":"1981","unstructured":"K-J. Raiha and E. Ukkonen. The shortest common supersequence problem over binary alphabet is NP-complete. Theoretical Computer Science, 16:187\u2013198, 1981.","journal-title":"Theoretical Computer Science"},{"key":"16_CR13","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":"English Translation from Kibernetika"},{"key":"16_CR14","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":"16_CR15","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"},{"key":"16_CR16","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M. Yannakakis","year":"1980","unstructured":"M. Yannakakis and F. Gavril. Edge dominating sets in graphs. SIAM J. Appl. Math., 38:364\u2013372, 1980.","journal-title":"SIAM J. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58094-8_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:10:52Z","timestamp":1619572252000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58094-8_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540580942","9783540484509"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-58094-8_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}