{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T09:38:23Z","timestamp":1780047503079,"version":"3.53.1"},"reference-count":9,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[2003,12,1]],"date-time":"2003-12-01T00:00:00Z","timestamp":1070236800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3516,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2003,12]]},"DOI":"10.1016\/s0022-0000(03)00078-3","type":"journal-article","created":{"date-parts":[[2003,6,30]],"date-time":"2003-06-30T17:29:01Z","timestamp":1056994141000},"page":"757-771","source":"Crossref","is-referenced-by-count":114,"title":["On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems"],"prefix":"10.1016","volume":"67","author":[{"given":"Krzysztof","family":"Pietrzak","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"issue":"1","key":"10.1016\/S0022-0000(03)00078-3_BIB1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/321921.321922","article-title":"Bounds on the complexity of the longest common subsequence problem","volume":"23","author":"Aho","year":"1976","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"10.1016\/S0022-0000(03)00078-3_BIB2","first-page":"49","article-title":"Parameterized complexity analysis in computational biology","volume":"11","author":"Bodlaender","year":"1995","journal-title":"CABIOS"},{"key":"10.1016\/S0022-0000(03)00078-3_BIB3","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0304-3975(94)00251-D","article-title":"The parameterized complexity of sequence alignment and consensus","volume":"147","author":"Bodlaender","year":"1994","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(03)00078-3_BIB4","series-title":"Parameterized Complexity, Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","author":"Downey","year":"1999"},{"key":"10.1016\/S0022-0000(03)00078-3_BIB5","doi-asserted-by":"crossref","unstructured":"K. Hakata, H. Imai, The longest common subsequence problem for small alphabet size between many strings. Proceedings of the third Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 670, Springer, Berlin, 1992.","DOI":"10.1007\/3-540-56279-6_99"},{"key":"10.1016\/S0022-0000(03)00078-3_BIB6","unstructured":"M.T. Hallett, An integrated complexity analysis of problems from computational biology, Ph.D. Dissertation, University of Victoria, 1996."},{"key":"10.1016\/S0022-0000(03)00078-3_BIB7","doi-asserted-by":"crossref","unstructured":"R.W. Irving, C.B. Fraser, Two algorithms for the longest common subsequence of three (or more) strings, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, Vol. 644, Springer, Berlin, 1992, pp. 214\u2013229.","DOI":"10.1007\/3-540-56024-6_18"},{"issue":"2","key":"10.1016\/S0022-0000(03)00078-3_BIB8","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/322063.322075","article-title":"The complexity of some problems on subsequences and supersequences","volume":"25","author":"Maier","year":"1978","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0022-0000(03)00078-3_BIB9","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0304-3975(81)90075-X","article-title":"The shortest common supersequence problem over a binary alphabet is NP-complete","volume":"16","author":"R\u00e4ih\u00e4","year":"1981","journal-title":"Theoret. Comput. Sci."}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000783?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000783?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,18]],"date-time":"2019-03-18T12:55:58Z","timestamp":1552913758000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000003000783"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,12]]},"references-count":9,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2003,12]]}},"alternative-id":["S0022000003000783"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(03)00078-3","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2003,12]]}}}