{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:45:47Z","timestamp":1759063547540},"reference-count":26,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,10,1]],"date-time":"2003-10-01T00:00:00Z","timestamp":1064966400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Algorithms"],"published-print":{"date-parts":[[2003,10]]},"DOI":"10.1016\/s0196-6774(03)00081-6","type":"journal-article","created":{"date-parts":[[2003,10,15]],"date-time":"2003-10-15T09:18:13Z","timestamp":1066209493000},"page":"192-216","source":"Crossref","is-referenced-by-count":27,"title":["Analogs & duals of the MAST problem for sequences & trees"],"prefix":"10.1016","volume":"49","author":[{"given":"Michael","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Hallett","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrike","family":"Stege","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0196-6774(03)00081-6_BIB001","series-title":"Foundations of Computer Science","author":"Aho","year":"1992"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB002","first-page":"49","article-title":"Parameterized complexity analysis in computational biology","volume":"11","author":"Bodlaender","year":"1995","journal-title":"Comput. Appl. Biosci."},{"key":"10.1016\/S0196-6774(03)00081-6_BIB003","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0304-3975(94)00251-D","article-title":"The parameterized complexity of the longest common subsequence problem","volume":"147","author":"Bodlaender","year":"1995","journal-title":"Theoret. Comput. Sci. A"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB004","unstructured":"D. Bryant, Building trees, hunting for trees, and comparing trees\u2014theory and methods in phylogenetic analysis, PhD thesis, Department of Mathematics, University of Canterbury, 1997"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB005","series-title":"Mathematics in the Archaeological and Historical Sciences","first-page":"387","article-title":"The recovery of trees from measures of dissimilarity","author":"Buneman","year":"1971"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB006","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s001530050069","article-title":"The parameterized complexity of short computation and factorization","volume":"36","author":"Cai","year":"1997","journal-title":"Arch. Math. Logic"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB007","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jagm.2001.1186","article-title":"Vertex cover: further observations and further improvements","volume":"41","author":"Chen","year":"2001","journal-title":"J. Algorithms"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB008","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1137\/S0097539792228228","article-title":"Fixed parameter tractability and completeness I: basic theory","volume":"24","author":"Downey","year":"1995","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0196-6774(03)00081-6_BIB009","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","article-title":"Fixed parameter tractability and completeness II: completeness for W[1]","volume":"141","author":"Downey","year":"1995","journal-title":"Theoret. Comput. Sci. A"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB010","series-title":"Feasible Mathematics II","first-page":"219","article-title":"Parametrized computational feasibility","author":"Downey","year":"1995"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB011","series-title":"Parameterized Complexity","author":"Downey","year":"1998"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB012","series-title":"The Future of Discrete Mathematics: Proceedings of the First DIMATIA Symposium, Stirin Castle, Czech Republic, June, 1997","article-title":"Parameterized complexity: a framework for systematically confronting computational intractability","author":"Downey","year":"1999"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB013","unstructured":"F. Dehne, A. Rau-Chaplin, U. Stege, P.J. Taillon, Solving large FPT problems on coarse grained parallel machines, Manuscript, 2001"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB014","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0020-0190(95)00110-X","article-title":"On the agreement of many trees","volume":"55","author":"Farach","year":"1995","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0196-6774(03)00081-6_BIB015","series-title":"9th International Sympsium, ISAAC '98","first-page":"347","article-title":"On the multiple gene duplication problem, Algorithms and Computation","volume":"1533","author":"Fellows","year":"1998"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB016","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB017","doi-asserted-by":"crossref","first-page":"132","DOI":"10.2307\/2412519","article-title":"Fitting the gene lineage into its species lineage: a parsimony strategy illustrated by cladograms constructed from globin sequences","volume":"28","author":"Goodman","year":"1979","journal-title":"Syst. Zool."},{"key":"10.1016\/S0196-6774(03)00081-6_BIB018","unstructured":"B. Ma, M. Li, L. Zhang, On reconstructing species trees from gene trees in term of duplications and losses, Recomb 98, in preparation"},{"issue":"2","key":"10.1016\/S0196-6774(03)00081-6_BIB019","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. ACM"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB020","unstructured":"M. Middendorf, Zur Komplexit\u00e4t von Einbettungsproblemen von Wortmengen, Dissertation, Fachbereich Mathematik, Universit\u00e4t Hannover, 1992"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB021","first-page":"58","article-title":"Maps between trees and cladistic analysis of historical associations among genes, organisms, and areas","volume":"43","author":"Page","year":"1994","journal-title":"Syst. Biol."},{"key":"10.1016\/S0196-6774(03)00081-6_BIB022","unstructured":"T. Przytycka, Private communication, 1997"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB023","unstructured":"U. Stege, Resolving conflicts in problems in computational biochemistry, PhD Dissertation ETH, Zurich, 2000"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB024","unstructured":"U. Stege, M. Fellows, An improved fixed-parameter tractable algorithm for vertex cover, Tech. Rep., ETH Zurich, 1999"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB025","first-page":"1","article-title":"Complexity of common subsequence and supersequence problems and related problems","volume":"25","author":"Timkovsky","year":"1990","journal-title":"Cybernetics"},{"key":"10.1016\/S0196-6774(03)00081-6_BIB026","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","article-title":"The string-to-string correction problem","volume":"21","author":"Wagner","year":"1974","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0196677403000816?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0196677403000816?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,19]],"date-time":"2019-02-19T14:51:37Z","timestamp":1550587897000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0196677403000816"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,10]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,10]]}},"alternative-id":["S0196677403000816"],"URL":"https:\/\/doi.org\/10.1016\/s0196-6774(03)00081-6","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[2003,10]]}}}