{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T07:19:30Z","timestamp":1778743170816,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540648482","type":"print"},{"value":"9783540685302","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-68530-8_9","type":"book-chapter","created":{"date-parts":[[2007,11,8]],"date-time":"2007-11-08T17:14:16Z","timestamp":1194542056000},"page":"103-114","source":"Crossref","is-referenced-by-count":11,"title":["Analogs and Duals of the MAST Problem for Sequences and Trees"],"prefix":"10.1007","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":"Chantal","family":"Korostensky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrike","family":"Stege","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,3,15]]},"reference":[{"key":"9_CR1","unstructured":"D. Bryant. \u201cBuilding Trees, Hunting for Trees, and Comparing Trees \u2014 Theory and Methods in Phylogenetic Analysis,\u201d Ph.D. Thesis. Department of Mathematics. University of Canterbury, 1997."},{"key":"9_CR2","first-page":"387","volume-title":"Mathematics in the Archaeological and Historical Sciences","author":"P. Buneman","year":"1971","unstructured":"P. Buneman. \u201cThe Recovery of Trees from Measures of Dissimilarity,\u201d In F. R. Hodson, D. G. Kendall, P. Tautu, editors, Mathematics in the Archaeological and Historical Sciences, pp. 387\u2013395. Edinburg University Press, Edinburgh, 1971."},{"key":"9_CR3","unstructured":"R. Downey and M. Fellows. \u201cFixed Parameter Tractability and Completeness III: Some Structural Aspects of the W-Hierarchy,\u201d in: K. Ambos-Spies, S. Homer and U. Sch\u00f6ning, editors, Complexity Theory: Current Research, Cambridge Univ. Press (1993), 166\u2013191."},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R. G. Downey","year":"1995","unstructured":"R. G. Downey and M. R. Fellows. \u201cFixed Parameter Tractability and Completeness I: Basic Theory,\u201d SIAM Journal of Computing 24 (1995), 873\u2013921.","journal-title":"SIAM Journal of Computing"},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R. G. Downey","year":"1995","unstructured":"R. G. Downey and M. R. Fellows. \u201cFixed Parameter Tractability and Completeness II: Completeness for W[1],\u201d Theoretical Computer Science A 141 (1995), 109\u2013131.","journal-title":"Theoretical Computer Science A"},{"key":"9_CR6","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-1-4612-2566-9_7","volume-title":"Feasible Mathematics II","author":"R. G. Downey","year":"1995","unstructured":"R. G. Downey and M. R. Fellows. \u201cParametrized Computational Feasibility,\u201d in: Feasible Mathematics II, P. Clote and J. Remmel (eds.) Birkhauser, Boston (1995) 219\u2013244."},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. Parameterized Complexity, Springer-Verlag, 1998.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0020-0190(95)00110-X","volume":"55","author":"M. Farach","year":"1995","unstructured":"M. Farach, T. Przytycka, and M. Thorup. \u201cOn the agreement of many trees\u201d Information Processing Letters 55 (1995), 297\u2013301.","journal-title":"Information Processing Letters"},{"key":"9_CR9","unstructured":"M. R. Fellows, M. T. Hallett, C. Korostensky, U. Stege. \u201cThe complexity of problems on sequences and trees.\u201d Technical Report, ETH-Zurich, 1998."},{"key":"9_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. \u201cComputers and Intractability: A Guide to the Theory of NP-Completeness,\u201d W. H. Freeman, San Francisco, 1979."},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"132","DOI":"10.2307\/2412519","volume":"28","author":"M. Goodman","year":"1979","unstructured":"M. Goodman, J. Czelusniak, G. W. Moore, A. E. Romero-Herrera and G. Matsuda. \u201cFitting the Gene Lineage into its Species Lineage: A parsimony strategy illustrated by cladograms constructed from globin sequences,\u201d Syst. Zool. (1979), 28, 132\u2013163.","journal-title":"Syst. Zool."},{"issue":"2","key":"9_CR12","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1006\/mpev.1996.0071","volume":"6","author":"R. Guig\u00f3","year":"1996","unstructured":"R. Guig\u00f3, I. Muchnik, and T. F. Smith. \u201cReconstruction of Ancient Molecular Phylogeny,\u201d Molecular Phylogenetics and Evolution (1996),6:2, 189\u2013213.","journal-title":"Molecular Phylogenetics and Evolution"},{"key":"9_CR13","unstructured":"B. Ma, M. Li, and L. Zhang. \u201cOn Reconstructing Species Trees from Gene Trees in Term of Duplications and Losses,\u201d Recomb 98, to appear."},{"issue":"2","key":"9_CR14","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"D. Maier. \u201cThe Complexity of Some Problems on Subsequences and Supersequences,\u201d J. ACM, 25,2 (1978), 322\u2013336.","journal-title":"J. ACM"},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"58","DOI":"10.2307\/2413581","volume":"43","author":"R. D. M. Page","year":"1994","unstructured":"R. D. M. Page. \u201cMaps between trees and cladistic analysis of historical associations among genes, organisms, and areas,\u201d Syst. Biol. 43 (1994), 58\u201377.","journal-title":"Syst. Biol."},{"key":"9_CR16","unstructured":"T. Przytycka. private communication, 1997."},{"issue":"2","key":"9_CR17","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1089\/cmb.1997.4.177","volume":"4","author":"L. Zhang","year":"1997","unstructured":"L. Zhang. \u201cOn a Mirkin-Muchnik-Smith Conjecture for Comparing Molecular Phylogenies,\u201d Journal of Computational Biology (1997) 4:2, 177\u2013187.","journal-title":"Journal of Computational Biology"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA\u2019 98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-68530-8_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T04:28:09Z","timestamp":1556944089000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-68530-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648482","9783540685302"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-68530-8_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1998]]}}}