{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:03:15Z","timestamp":1787385795163,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1997,12]]},"abstract":"<jats:p>The maximum agreement subtree approach is one method of reconciling different evolutionary trees for the same set of species. An agreement subtree enables choosing a subset of the species for whom the restricted subtree is equivalent (under a suitable definition) in all given evolutionary trees.<\/jats:p>\n                  <jats:p>Recently, dynamic programming ideas were used to provide polynomial time algorithms for finding a maximum homeomorphic agreement subtree of two trees. Generalizing these methods to sets of more than two trees yields algorithms that are exponential in the number of trees. Unfortunately, it turns out that in reality one is usually presented with more than two trees, sometimes as many as thousands of trees.<\/jats:p>\n                  <jats:p>In this paper we prove that the maximum homeomorphic agreement subtree problem is $\\cal{NP}$-complete for three trees with unbounded degrees. We then show an approximation algorithm of time O(kn5) for choosing the species that are not in a maximum agreement subtree of a set of k trees. Our approximation is guaranteed to provide a set that is no more than 4 times the optimum solution.<\/jats:p>\n                  <jats:p>While the set of evolutionary trees may be large in practice, the trees usually have very small degrees, typically no larger than three. We develop a new method for finding a maximum agreement subtree of k trees, of which one has degree bounded by d. This new method enables us to find a maximum agreement subtree in time O(knd + 1+ n2d).<\/jats:p>","DOI":"10.1137\/s0097539794269461","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1656-1669","source":"Crossref","is-referenced-by-count":88,"title":["Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms"],"prefix":"10.1137","volume":"26","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dmitry","family":"Keselman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"A. Amir and D. Keselman,\n                      Maximum agreement subtree in a set of evolutionary trees \u2010 Metrics and efficient algorithms\n                      , in Proc. 35th IEEE Symposium on Foundations of Computer Science, Santa Fe, NM, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 758\u2013769.","DOI":"10.1109\/SFCS.1994.365717"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(86)90038-2"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01908061"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"M. Farach, S. Kannan, and T. Warnow,\n                      A robust model for finding optimal evolutionary trees\n                      , in Proc. 25th Annual ACM Symposium on the Theory of Computing, San Diego, CA, ACM, New York, 1993, pp. 137\u2013145.","DOI":"10.1145\/167088.167132"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"M. Farach, T. M. Przytycka, and M. Thorup,\n                      On the agreement of many trees\n                      , in Proc. 3rd European Symposium on Algorithms, Corfo, Greece, 1995, pp. 381\u2013393.","DOI":"10.1007\/3-540-60313-1_157"},{"key":"R6","unstructured":"Martin Farach, Mikkel Thorup, Fast comparison of evolutionary trees, ACM, New York, 1994, 481\u201348895c:92009"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01908078"},{"key":"R8","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R9","unstructured":"W. Goddard, E. Kubicka, G. Kubicki, and F. R. McMorris,\n                      Agreement subtrees, metric and consensus for labeled binary trees\n                      , DIMACS Workshop on Partitioning Data Sets, Rutgers University, New Brunswick, NJ, 1993."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/66.1.7"},{"key":"R11","unstructured":"A. D. Gordon,\n                      On the assessment and comparison of classifications\n                      , in Analyse de Donn\u00e9es et Informatique, R. Tomassone, ed., INRIA, 1980, pp. 149\u2013160."},{"key":"R12","unstructured":"J. A. Hartigan,\n                      Clustering algorithms\n                      , John Wiley, New York, 1975."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"J. Hein, T. Jiang, L. Wang, and K. Zhang,\n                      On the Complexity of Comparing Evolutionary Trees\n                      , in Proc. 6th Symposium on Combinational Pattern Matching, Helsinki, Finland, 1995, pp. 177\u2013190.","DOI":"10.1007\/3-540-60044-2_42"},{"key":"R14","unstructured":"E. Kubicka, G. Kubicki, and F. R. McMorris,\n                      An algorithm to find agreement subtrees\n                      , J. Classification, 1992."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1006\/bulm.2000.0219"},{"key":"R16","first-page":"371","volume":"2","author":"Smolenskii E. A.","year":"1962","journal-title":"Jurnal Vicisl. Mat. i Matem. Fiz"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90181-8"},{"key":"R18","first-page":"126","volume":"42","author":"Steel M. A.","year":"1993","journal-title":"Syst. Biol."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794269461","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:43Z","timestamp":1787335963000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794269461"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,12]]},"references-count":18,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1997,12]]}},"alternative-id":["10.1137\/S0097539794269461"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794269461","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,12]]}}}