{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,3]],"date-time":"2024-08-03T15:37:09Z","timestamp":1722699429451},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2017,6,6]],"date-time":"2017-06-06T00:00:00Z","timestamp":1496707200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00453-017-0330-4","type":"journal-article","created":{"date-parts":[[2017,6,6]],"date-time":"2017-06-06T14:18:32Z","timestamp":1496758712000},"page":"2453-2477","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Fast Compatibility Testing for Rooted Phylogenetic Trees"],"prefix":"10.1007","volume":"80","author":[{"given":"Yun","family":"Deng","sequence":"first","affiliation":[]},{"given":"David","family":"Fern\u00e1ndez-Baca","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,6]]},"reference":[{"issue":"3","key":"330_CR1","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"AV Aho","year":"1981","unstructured":"Aho, A.V., Sagiv, Y., Szymanski, T.G., Ullman, J.D.: Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J. Comput. 10(3), 405\u2013421 (1981)","journal-title":"SIAM J. Comput."},{"key":"330_CR2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.2307\/1222480","volume":"41","author":"BR Baum","year":"1992","unstructured":"Baum, B.R.: Combining trees as a way of combining data sets for phylogenetic inference, and the desirability of combining gene trees. Taxon 41, 3\u201310 (1992)","journal-title":"Taxon"},{"key":"330_CR3","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1038\/nature05634","volume":"446","author":"ORP Bininda-Emonds","year":"2007","unstructured":"Bininda-Emonds, O.R.P., Cardillo, M., Jones, K.E., MacPhee, R.D.E., Beck, R.M.D., Grenyer, R., Price, S.A., Vos, R.A., Gittleman, J.L., Purvis, A.: The delayed rise of present-day mammals. Nature 446, 507\u2013512 (2007)","journal-title":"Nature"},{"key":"330_CR4","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/j.tcs.2005.10.033","volume":"351","author":"D Bryant","year":"2006","unstructured":"Bryant, D., Lagergren, J.: Compatibility of unrooted phylogenetic trees is FPT. Theor. Comput. Sci. 351, 296\u2013302 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"330_CR5","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P Buneman","year":"1974","unstructured":"Buneman, P.: A characterisation of rigid circuit graphs. Discrete Math. 9, 205\u2013212 (1974)","journal-title":"Discrete Math."},{"key":"330_CR6","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"issue":"1","key":"330_CR7","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"330_CR8","doi-asserted-by":"crossref","unstructured":"Deng, Y., Fern\u00e1ndez-Baca, D.: Fast compatibility testing for phylogenies with nested taxa. In: Frith, M.C., Pedersen, C.N.S. (eds.) Algorithms in Bioinformatics. In: 16th International Workshop, WABI 2016, Aarhus, Denmark, Aug 22\u201324, 2016. Proceedings, volume 9838 of Lecture Notes in Computer Science, pp. 90\u2013101. Springer (2016)","DOI":"10.1007\/978-3-319-43681-4_8"},{"key":"330_CR9","unstructured":"Deng, Y., Fern\u00e1ndez-Baca, D.: Fast compatibility testing for rooted phylogenetic trees. In: Grossi, R., Lewenstein, M. (eds.) Proceedings of 27th Annual Symposium on Combinatorial Pattern Matching, volume\u00a054 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 12:1\u201312:12, Dagstuhl, Germany, 2016. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik"},{"issue":"1","key":"330_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/322234.322235","volume":"28","author":"S Even","year":"1981","unstructured":"Even, S., Shiloach, Y.: An on-line edge-deletion problem. J. ACM 28(1), 1\u20134 (1981)","journal-title":"J. ACM"},{"key":"330_CR11","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1016\/j.mbs.2006.11.005","volume":"208","author":"S Gr\u00fcnewald","year":"2007","unstructured":"Gr\u00fcnewald, S., Steel, M., Swenson, M.S.: Closure operations in phylogenetics. Math. Biosci. 208, 521\u2013537 (2007)","journal-title":"Math. Biosci."},{"key":"330_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00009268","volume":"24","author":"MR Henzinger","year":"1999","unstructured":"Henzinger, M.R., King, V., Warnow, T.: Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica 24, 1\u201313 (1999)","journal-title":"Algorithmica"},{"issue":"41","key":"330_CR13","doi-asserted-by":"crossref","first-page":"12764","DOI":"10.1073\/pnas.1423041112","volume":"112","author":"CE Hinchliff","year":"2015","unstructured":"Hinchliff, C.E., Smith, S.A., Allman, J.F., Burleigh, J.G., Chaudhary, R., Coghill, L.M., Crandall, K.A., Deng, J., Drew, B.T., Gazis, R., Gude, K., Hibbett, D.S., Katz, L.A., Laughinghouse IV, H.D., McTavish, E.J., Midford, P.E., Owen, C.L., Reed, R.H., Reesk, J.A., Soltis, D.E., Williams, T., Cranston, K.A.: Synthesis of phylogeny and taxonomy into a comprehensive tree of life. Proc. Natl. Acad. Sci. 112(41), 12764\u201312769 (2015)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"4","key":"330_CR14","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J Holm","year":"2001","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723\u2013760 (2001)","journal-title":"J. ACM"},{"key":"330_CR15","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/945394.945398","volume":"6","author":"R Iyer","year":"2001","unstructured":"Iyer, R., Karger, D., Rahul, H., Thorup, M.: An experimental study of polylogarithmic, fully dynamic, connectivity algorithms. J. Exp. Algorithmics 6, 4 (2001)","journal-title":"J. Exp. Algorithmics"},{"key":"330_CR16","doi-asserted-by":"crossref","unstructured":"Jansson, J., Shen, C., Sung, W.: Improved algorithms for constructing consensus trees. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pp. 1800\u20131813. New Orleans, Louisiana, USA, Jan 6\u20138, 2013","DOI":"10.1137\/1.9781611973105.129"},{"issue":"3","key":"330_CR17","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1137\/S0097539702406510","volume":"33","author":"I Pe\u2019er","year":"2004","unstructured":"Pe\u2019er, I., Pupko, T., Shamir, R., Sharan, R.: Incomplete directed perfect phylogeny. SIAM J. Comput. 33(3), 590\u2013607 (2004)","journal-title":"SIAM J. Comput."},{"key":"330_CR18","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/1055-7903(92)90035-F","volume":"1","author":"MA Ragan","year":"1992","unstructured":"Ragan, M.A.: Phylogenetic inference based on matrix representation of trees. Mol. Phylogenet. Evol. 1, 53\u201358 (1992)","journal-title":"Mol. Phylogenet. Evol."},{"issue":"5885","key":"330_CR19","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1126\/science.1154449","volume":"321","author":"MJ Sanderson","year":"2008","unstructured":"Sanderson, M.J.: Phylogenetic signal in the eukaryotic tree of life. Science 321(5885), 121\u2013123 (2008)","journal-title":"Science"},{"key":"330_CR20","series-title":"Oxford Lecture Series in Mathematics","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford Lecture Series in Mathematics. Oxford University Press, Oxford (2003)"},{"key":"330_CR21","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02618470","volume":"9","author":"MA Steel","year":"1992","unstructured":"Steel, M.A.: The complexity of reconstructing trees from qualitative characters and subtrees. J. Classif. 9, 91\u2013116 (1992)","journal-title":"J. Classif."},{"key":"330_CR22","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 343\u2013350. ACM (2000)","DOI":"10.1145\/335305.335345"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0330-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0330-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0330-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,24]],"date-time":"2024-06-24T16:02:58Z","timestamp":1719244978000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0330-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,6]]},"references-count":22,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["330"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0330-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,6]]}}}