{"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":1787385795841,"version":"build-2736575974"},"reference-count":50,"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":[[1998,1]]},"abstract":"<jats:p>\n                    An evolutionary tree is a rooted tree where each internal vertex has at least two children and where the leaves are labeled with distinct symbols representing species. Evolutionary trees are useful for modeling the evolutionary history of species. An agreement subtree of two evolutionary trees is an evolutionary tree which is also a topological subtree of the two given trees. We give an algorithm to determine the largest possible number of leaves in any agreement subtree of two trees T\n                    <jats:sub>1<\/jats:sub>\n                    and T\n                    <jats:sub>2<\/jats:sub>\n                    with n leaves each. If the maximum degree d of these trees is bounded by a constant, the time complexity is O(n log\n                    <jats:sup>2<\/jats:sup>\n                    n) and is within a log n factor of optimal. For general d, this algorithm runs in O(nd\n                    <jats:sup>2<\/jats:sup>\n                    log d log\n                    <jats:sup>2<\/jats:sup>\n                    n) time or alternatively in $O(ndsqrt{d}\\log^3{n})$ time.\n                  <\/jats:p>","DOI":"10.1137\/s0097539795283504","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1592-1616","source":"Crossref","is-referenced-by-count":25,"title":["Tree Contractions and Evolutionary Trees"],"prefix":"10.1137","volume":"27","author":[{"given":"Ming-Yang","family":"Kao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90017-5"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244587"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321922"},{"key":"R4","unstructured":"A. Aho, D\u017e. Hopkroft, D\u017e. Ul\u2019man, Postroenie i analiz vychislitelnykh algoritmov, \u201cMir\u201d, 1979, 536\u20130, Translated by A. O. Slisenko; Edited by Ju. V. Matijasevi\u010d80g:68036"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0210030"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840365"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Hans Bodlaender, Mike Fellows, Tandy Warnow, Two strikes against perfect phylogeny, Lecture Notes in Comput. Sci., Vol. 623, Springer, Berlin, 1992, 273\u201328394j:92003","DOI":"10.1007\/3-540-55719-9_80"},{"key":"R8","unstructured":"R. Cole and R. Hariharan,\n                      An O(nlogn) algorithm for the maximum agreement subtree problem for binary trees\n                      , in Proceedings of the 7th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, 1996, pp. 323\u2013332."},{"key":"R9","volume-title":"Introduction to algorithms","author":"Manber Udi","year":"1989"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-5193(87)80263-1"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0893-9659(92)90026-6"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01188585"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Martin Farach, Teresa Przytycka, Mikkel Thorup, Computing the agreement of trees with bounded degrees, Lecture Notes in Comput. Sci., Vol. 979, Springer, Berlin, 1995, 381\u20133931460752","DOI":"10.1007\/3-540-60313-1_157"},{"key":"R14","unstructured":"Martin Farach, Mikkel Thorup, Fast comparison of evolutionary trees, ACM, New York, 1994, 481\u201348895c:92009"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"M. Farach and M. Thorup,\n                      Optimal evolutionary tree comparison by sparse dynamic programming (extended abstract)\n                      , in Proceedings of the 35th Annual IEEE Symposium on Foundationsof Computer Science, 1994, pp. 770\u2013779.","DOI":"10.1109\/SFCS.1994.365716"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1086\/412935"},{"key":"R17","unstructured":"J. Felsenstein,\n                      Inferring evolutionary trees from DNA sequences\n                      , in Statistical Analysis of DNA Sequence Data, B. Weir, ed., Marcel Dekker, New York, 1983, pp. 133\u2013150."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.ge.22.120188.002513"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01908078"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1159\/000156418"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0218069"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"H. Gazit, G. L. Miller, and S. H. Teng,\n                      Optimal tree contraction in the EREW model\n                      , in Concurrent Computations: Algorithms, Architecture, and Technology, S. T. and B. W. Dickinson and S. Schwartz, eds., Plenum, New York, 1988, pp. 139\u2013156.","DOI":"10.1007\/978-1-4684-5511-3_9"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90014-1"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230210104"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/S0092-8240(89)80102-8"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.2307\/2992397"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(82)90027-X"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360861"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1145\/322033.322044"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90037-6"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1145\/359581.359603"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"T. Jiang, E. L. Lawler, and L. Wang,\n                      Aligning sequences via an evolutionary tree: Complexity and approximation\n                      , in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994, pp. 760\u2013769.","DOI":"10.1145\/195058.195454"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0035"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791222171"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794269461"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(81)90233-2"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"S. Kosaraju, Arthur Delcher, Optimal parallel evaluation of tree\u2010structured computations by raking (extended abstract), Lecture Notes in Comput. Sci., Vol. 319, Springer, New York, 1988, 101\u20131101017464","DOI":"10.1007\/BFb0040378"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202269"},{"key":"R40","unstructured":"G. L. Miller and J. H. Reif,\n                      \n                        Parallel tree contraction, part\n                        1\n                        : Fundamentals\n                      \n                      , in Advances in Computing Research: Randomness and Computation, Vol. 5, S. Micali, ed., JAI Press, Greenwich, CT, 1989, pp. 47\u201372."},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1137\/0220070"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1007\/BF01586040"},{"key":"R43","first-page":"403","volume":"3","author":"Penny D.","year":"1986","journal-title":"Molecular Biology and Evolution","ISSN":"https:\/\/id.crossref.org\/issn\/0737-4038","issn-type":"print"},{"key":"R44","first-page":"945","volume":"9","author":"Rzhetsky A.","year":"1992","journal-title":"Molecular Biology and Evolution","ISSN":"https:\/\/id.crossref.org\/issn\/0737-4038","issn-type":"print"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1137\/0217079"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1007\/BF02618470"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90181-8"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1007\/s004539900051"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1018"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321923"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795283504","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:13Z","timestamp":1787336053000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795283504"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":50,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795283504"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795283504","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}