{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T22:10:04Z","timestamp":1739052604014,"version":"3.37.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,4,7]],"date-time":"2009-04-07T00:00:00Z","timestamp":1239062400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,2]]},"DOI":"10.1007\/s00453-009-9303-6","type":"journal-article","created":{"date-parts":[[2009,4,6]],"date-time":"2009-04-06T17:31:40Z","timestamp":1239039100000},"page":"195-214","source":"Crossref","is-referenced-by-count":5,"title":["Improved Algorithms for Maximum Agreement and\u00a0Compatible Supertrees"],"prefix":"10.1007","volume":"59","author":[{"given":"Viet Tung","family":"Hoang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wing-Kin","family":"Sung","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,4,7]]},"reference":[{"issue":"6","key":"9303_CR1","doi-asserted-by":"crossref","first-page":"1656","DOI":"10.1137\/S0097539794269461","volume":"26","author":"A. Amir","year":"1997","unstructured":"Amir, A., Keselman, D.: Maximum agreement subtree in a set of evolutionary trees: metrics and efficient algorithms. SIAM J.\u00a0Comput. 26(6), 1656\u20131669 (1997)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9303_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/978-3-540-27801-6_15","volume-title":"Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM 2004)","author":"V. Berry","year":"2004","unstructured":"Berry, V., Nicolas, F.: Maximum agreement and compatible supertrees. In: Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM 2004). Lecture Notes in Computer Science, vol. 3109, pp. 205\u2013219. Springer, Berlin (2004)"},{"key":"9303_CR3","unstructured":"Bryant, D.: Building trees, hunting for trees, and comparing trees: theory and methods in phylogenetic analysis. PhD thesis, University of Canterbury, Christchurch, New Zealand (1997)"},{"issue":"5","key":"9303_CR4","doi-asserted-by":"crossref","first-page":"1385","DOI":"10.1137\/S0097539796313477","volume":"30","author":"R. Cole","year":"2000","unstructured":"Cole, R., Farach-Colton, M., Hariharan, R., Przytycka, T., Thorup, M.: An O(nlog\u2009n) algorithm for the maximum agreement subtree problem for binary trees. SIAM J.\u00a0Comput. 30(5), 1385\u20131404 (2000)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9303_CR5","unstructured":"Farach, M., Thorup, M.: Fast comparison of evolutionary trees. In: Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201994), pp.\u00a0481\u2013488 (1994)"},{"issue":"1","key":"9303_CR6","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1137\/S0097539794262422","volume":"26","author":"M. Farach","year":"1997","unstructured":"Farach, M., Thorup, M.: Sparse dynamic programming for evolutionary-tree comparison. SIAM J.\u00a0Comput. 26(1), 210\u2013230 (1997)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9303_CR7","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0020-0190(95)00110-X","volume":"55","author":"M. Farach","year":"1995","unstructured":"Farach, M., Przytycka, T., Thorup, M.: On the agreement of many trees. Inf. Process. Lett. 55, 297\u2013301 (1995)","journal-title":"Inf. Process. Lett."},{"key":"9303_CR8","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01908078","volume":"2","author":"C.R. Finden","year":"1985","unstructured":"Finden, C.R., Gordon, A.D.: Obtaining common pruned trees. J.\u00a0Classif. 2, 255\u2013276 (1985)","journal-title":"J.\u00a0Classif."},{"key":"9303_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1007\/3-540-44696-6_12","volume-title":"Proceedings of the 1st Workshop on Algorithms in Bioinformatics (WABI 2001)","author":"G. Ganapathysaravanabavan","year":"2001","unstructured":"Ganapathysaravanabavan, G., Warnow, T.: Finding a maximum compatible tree for a bounded number of trees with bounded degree is solvable in polynomial time. In: Proceedings of the 1st Workshop on Algorithms in Bioinformatics (WABI 2001). Lecture Notes in Computer Science, vol. 2149, pp. 156\u2013163. Springer, Berlin (2001)"},{"key":"9303_CR10","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/BF01894195","volume":"3","author":"A.G. Gordon","year":"1986","unstructured":"Gordon, A.G.: Consensus supertrees: the synthesis of rooted trees containing overlapping sets of labelled leaves. J.\u00a0Classif. 3, 335\u2013348 (1986)","journal-title":"J.\u00a0Classif."},{"key":"9303_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/978-3-540-73437-6_28","volume-title":"Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007)","author":"S. Guillemot","year":"2007","unstructured":"Guillemot, S., Berry, V.: Fixed-parameter tractability of the maximum agreement supertree problem. In: Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007). Lecture Notes in Computer Science, vol. 4580, pp. 274\u2013285. Springer, Berlin (2007)"},{"key":"9303_CR12","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0166-218X(96)00062-5","volume":"71","author":"J. Hein","year":"1996","unstructured":"Hein, J., Jiang, T., Wang, L., Zhang, K.: On the complexity of comparing evolutionary trees. Discrete Appl. Math. 71, 153\u2013169 (1996)","journal-title":"Discrete Appl. Math."},{"key":"9303_CR13","first-page":"361","volume-title":"25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)","author":"V.T. Hoang","year":"2008","unstructured":"Hoang, V.T., Sung, W.-K.: Fixed parameter polynomial time algorithms for maximum agreement and compatible supertrees. In: Albers, S., Weil, P. (eds.) 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), pp. 361\u2013372. Dagstuhl, Germany (2008). Internationales Begegnungs- und Forschungszentrum f\u00fcr Informatik (IBFI), Schloss Dagstuhl, Germany"},{"key":"9303_CR14","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/s00453-004-1147-5","volume":"43","author":"J. Jansson","year":"2005","unstructured":"Jansson, J., Ng, J.H.-K., Sadakane, K., Sung, W.-K.: Rooted maximum agreement supertrees. Algorithmica 43, 293\u2013307 (2005)","journal-title":"Algorithmica"},{"issue":"6","key":"9303_CR15","doi-asserted-by":"crossref","first-page":"1592","DOI":"10.1137\/S0097539795283504","volume":"27","author":"M.-Y. Kao","year":"1998","unstructured":"Kao, M.-Y.: Tree contractions and evolutionary trees. SIAM J.\u00a0Comput. 27(6), 1592\u20131616 (1998)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9303_CR16","doi-asserted-by":"crossref","unstructured":"Kao, M.-Y., Lam, T.-W., Przytycka, T., Sung, W.-K., Ting, H.-F.: General techniques for comparing unrooted evolutionary trees. In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC\u201997), pp.\u00a054\u201365 (1997)","DOI":"10.1145\/258533.258550"},{"issue":"2","key":"9303_CR17","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1006\/jagm.2001.1163","volume":"40","author":"M.-Y. Kao","year":"2001","unstructured":"Kao, M.-Y., Lam, T.-W., Sung, W.-K., Ting, H.-F.: An even faster and more unifying algorithm for comparing trees via unbalanced bipartite matchings. J.\u00a0Algorithms 40(2), 212\u2013233 (2001)","journal-title":"J.\u00a0Algorithms"},{"key":"9303_CR18","doi-asserted-by":"crossref","unstructured":"Maddison, D.R., Schulz, K.-S. (eds.): The tree of life web project. Internet address: http:\/\/tolweb.org (1996\u20132006)","DOI":"10.11646\/zootaxa.1668.1.4"},{"issue":"1\u20133","key":"9303_CR19","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0166-218X(00)00202-X","volume":"105","author":"C. Semple","year":"2000","unstructured":"Semple, C., Steel, M.: A supertree method for rooted trees. Discrete Appl. Math. 105(1\u20133), 147\u2013158 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9303_CR20","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02618470","volume":"9","author":"M. Steel","year":"1992","unstructured":"Steel, M.: The complexity of reconstructing trees from qualitative characters and subtrees. J. Classif. 9(1), 91\u2013116 (1992)","journal-title":"J. Classif."},{"key":"9303_CR21","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0020-0190(93)90181-8","volume":"48","author":"M. Steel","year":"1993","unstructured":"Steel, M., Warnow, T.: Kaikoura tree theorems: Computing the maximum agreement subtree. Inf. Process. Lett. 48, 77\u201382 (1993)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9303-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9303-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9303-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T21:34:42Z","timestamp":1739050482000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9303-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,7]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["9303"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9303-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2009,4,7]]}}}