{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:23:00Z","timestamp":1742383380553},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540223412"},{"type":"electronic","value":"9783540278016"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27801-6_15","type":"book-chapter","created":{"date-parts":[[2010,9,5]],"date-time":"2010-09-05T19:00:15Z","timestamp":1283713215000},"page":"205-219","source":"Crossref","is-referenced-by-count":10,"title":["Maximum Agreement and Compatible Supertrees"],"prefix":"10.1007","author":[{"given":"Vincent","family":"Berry","sequence":"first","affiliation":[]},{"given":"Fran\u00e7ois","family":"Nicolas","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0012-365X(00)00199-0","volume":"229","author":"J. Alber","year":"2001","unstructured":"Alber, J., Gramm, J., Niedermeier, R.: Faster exact algorithms for hard problems: a parameterized point of view. Disc. Math.\u00a0229, 3\u201327 (2001)","journal-title":"Disc. Math."},{"issue":"3","key":"15_CR2","doi-asserted-by":"publisher","first-page":"1656","DOI":"10.1137\/S0097539794269461","volume":"26","author":"A. Amir","year":"1997","unstructured":"Amir, A., Keselman, D.: Amir and D. Keselman. Maximum agreement subtree in a set of evolutionary trees: metrics and efficient algorithm. SIAM J. on Comp.\u00a026(3), 1656\u20131669 (1997)","journal-title":"SIAM J. on Comp."},{"key":"15_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.2307\/1222480","volume":"41","author":"B.R. 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\u00a041, 3\u201310 (1992)","journal-title":"Taxon"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldwasser, S., Lund, C., Russeli, A.: Efficient probabilistically checkable proofs and applications to approximations. In: Proceedings of the Twenty- Fifth Annual A.C.M. Symposium on Theory of Computing, pp. 294\u2013304 (1993)","DOI":"10.1145\/167088.167174"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"V. Berry and F. Nicolas. Maximum agreement and compatible supertrees(2004), (available from http:\/\/www.lirmm.fr\/~vberry ) 04045, LIRMM,","DOI":"10.1007\/978-3-540-27801-6_15"},{"key":"15_CR6","first-page":"497","volume":"47","author":"O.R.P. Bininda-Edmonds","year":"1998","unstructured":"Bininda-Edmonds, O.R.P., Bryant, H.N.: Properties of matrix representation with parsimony analyses. Syst. Biol.\u00a047, 497\u2013508 (1998)","journal-title":"Syst. Biol."},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Bininda-Edmonds, O.R.P., Gittleman, J.L., Steel, M.A.: The (super)tree of life: procedures, problems, and prospects. Ann. Rev. Ecol. Syst (2002)","DOI":"10.1146\/annurev.ecolsys.33.010802.150511"},{"issue":"4","key":"15_CR8","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1080\/106351501750435112","volume":"50","author":"O.R.P. Bininda-Edmonds","year":"2001","unstructured":"Bininda-Edmonds, O.R.P., Sanderson, M.J.: Assessment of the accuracy of matrix representation with parsimony analysis supertree construction. Syst. Biol.\u00a050(4), 565\u2013579 (2001)","journal-title":"Syst. Biol."},{"key":"15_CR9","unstructured":"Bryant, D.: Building trees, hunting for trees and comparing trees. PhD thesis, University of Canterbury, Department of Math. (1997)"},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1006\/aama.1995.1020","volume":"16","author":"D. Bryant","year":"1995","unstructured":"Bryant, D., Steel, M.A.: Extension operations on sets of leaf-labelled trees. Adv. Appl. Math.\u00a016, 425\u2013453 (1995)","journal-title":"Adv. Appl. Math."},{"key":"15_CR11","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1090\/dimacs\/061\/10","volume":"61","author":"D. Chen","year":"2003","unstructured":"Chen, D., Diao, L., Eulenstein, O., Fernandez-Baca, D.: Flipping: a supertree construction method. DIMACS Series in Disc. Math. and Theor. Comp. Sci.\u00a061, 135\u2013160 (2003)","journal-title":"DIMACS Series in Disc. Math. and Theor. Comp. Sci."},{"issue":"5","key":"15_CR12","doi-asserted-by":"publisher","first-page":"1385","DOI":"10.1137\/S0097539796313477","volume":"30","author":"R. Cole","year":"2001","unstructured":"Cole, R., Farach, M., Hartigan, R.: Przytycka T., and M. Thorup. An O(n log n) algorithm for the maximum agreement subtree problem for binary trees. SIAM J.on Computing\u00a030(5), 1385\u20131404 (2001)","journal-title":"SIAM J.on Computing"},{"key":"15_CR13","unstructured":"Cole, R., Hariharan, R.: Dynamic lca queries on trees. In: Proc. of the 10th ann. ACM-SIAM symp. on Disc. alg (SODA 1999), pp. 235\u2013244 (1999)"},{"key":"15_CR14","first-page":"73","volume":"69","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R., Stege, U.: Computational tractability: The view from mars. Bull. of the Europ. Assoc. for Theoret. Comp. Sci.\u00a069, 73\u201397 (1999)","journal-title":"Bull. of the Europ. Assoc. for Theoret. Comp. Sci."},{"issue":"6","key":"15_CR15","doi-asserted-by":"publisher","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.: Agreement of many bounded degree evolutionary trees. Inf. Proc. Letters\u00a055(6), 297\u2013301 (1995)","journal-title":"Inf. Proc. Letters"},{"key":"15_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/3-540-44696-6_12","volume-title":"Algorithms in Bioinformatics","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: Gascuel, O., Moret, B.M.E. (eds.) WABI 2001. LNCS, vol.\u00a02149, pp. 156\u2013163. Springer, Heidelberg (2001)"},{"key":"15_CR17","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1023\/A:1009833626004","volume":"3","author":"L. Gasieniec","year":"1999","unstructured":"Gasieniec, L., Jansson, J., Lingas, A., Ostlin, A.: On the complexity of constructing evolutionary trees. J. of Combin. Optim.\u00a03, 183\u2013197 (1999)","journal-title":"J. of Combin. Optim."},{"key":"15_CR18","doi-asserted-by":"publisher","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. of Classif.\u00a03, 335\u2013346 (1986)","journal-title":"J. of Classif."},{"issue":"2","key":"15_CR19","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/PL00009212","volume":"21","author":"A. Gupta","year":"1998","unstructured":"Gupta, A., Nishimura, N.: Gupta and N. Algorithmica\u00a021(2), 183\u2013210 (1998)","journal-title":"Algorithmica"},{"key":"15_CR20","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.3230210104","volume":"21","author":"D. Gusfield","year":"1991","unstructured":"Gusfield, D.: Efficient algorithms for inferring evolutionary trees. Networks\u00a021, 19\u201328 (1991)","journal-title":"Networks"},{"issue":"2","key":"15_CR21","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0893-9659(96)00012-2","volume":"9","author":"A.M. Hamel","year":"1996","unstructured":"Hamel, A.M., Steel, M.A.: Finding a maximum compatible tree is NP-hard for sequences and trees. Appl. Math. Lett.\u00a09(2), 55\u201359 (1996)","journal-title":"Appl. Math. Lett."},{"key":"15_CR22","first-page":"338","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestor. Computer and System Science\u00a013, 338\u2013355 (1984)","journal-title":"Computer and System Science"},{"key":"15_CR23","doi-asserted-by":"publisher","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. Disc. Appl. Math.\u00a071, 153\u2013169 (1996)","journal-title":"Disc. Appl. Math."},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"Jansson, J., Ng, J.H.-K., Sadakane, K., Sung, W.-K.: Rooted maximum agreement supertrees. In: Proceedings of the Sixth Latin American Symposium on Theoretical Informatics, LATIN (2004) (in press)","DOI":"10.1007\/978-3-540-24698-5_53"},{"key":"15_CR25","first-page":"438","volume-title":"Proc. of the 8th Ann. Europ. Symp. Alg. (ESA)","author":"M.Y. Kao","year":"1999","unstructured":"Kao, M.Y., Lam, T.W., Sung, W.K., Ting, H.F.: A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees. In: Proc. of the 8th Ann. Europ. Symp. Alg (ESA), pp. 438\u2013449. Springer, New York (1999)"},{"key":"15_CR26","doi-asserted-by":"publisher","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. of Algo.\u00a040, 212\u2013233 (2001)","journal-title":"J. of Algo."},{"key":"15_CR27","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S1570-8667(03)00009-1","volume":"1","author":"R. Niedermeier","year":"2003","unstructured":"Niedermeier, R., Rossmanith, P.: An efficient fixed parameter algorithm for 3-Hitting Set. Journal of Discrete Algorithms\u00a01, 89\u2013102 (2003)","journal-title":"Journal of Discrete Algorithms"},{"key":"15_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1007\/3-540-45784-4_41","volume-title":"Algorithms in Bioinformatics","author":"R. Page","year":"2002","unstructured":"Page, R.: Modified mincut supertrees. In: Guig\u00f3, R., Gusfield, D. (eds.) WABI 2002. LNCS, vol.\u00a02452, pp. 538\u2013551. Springer, Heidelberg (2002)"},{"key":"15_CR29","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1093\/sysbio\/44.2.251","volume":"44","author":"A. Purvis","year":"1995","unstructured":"Purvis, A.: A modification to Baum and Ragan\u2019s method for combining phylogenetic trees. Syst. Biol.\u00a044, 251\u2013255 (1995)","journal-title":"Syst. Biol."},{"key":"15_CR30","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0303-2647(92)90007-L","volume":"28","author":"M.A. Ragan","year":"1992","unstructured":"Ragan, M.A.: Matrix representation in reconstructing phylogenetic relationships among the eukaryots. Biosystems\u00a028, 47\u201355 (1992)","journal-title":"Biosystems"},{"key":"15_CR31","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1093\/sysbio\/45.2.247","volume":"45","author":"F. Ronquist","year":"1996","unstructured":"Ronquist, F.: Matrix representation of trees, redundancy, and weighting. Syst. Biol.\u00a045, 247\u2013253 (1996)","journal-title":"Syst. Biol."},{"key":"15_CR32","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/S0166-218X(00)00202-X","volume":"105","author":"C. Semple","year":"2000","unstructured":"Semple, C., Steel, M.A.: A supertree method for rooted trees. Disc. Appl. Math.\u00a0105, 147\u2013158 (2000)","journal-title":"Disc. Appl. Math."},{"key":"15_CR33","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(93)90181-8","volume":"48","author":"M.A. Steel","year":"1993","unstructured":"Steel, M.A., Warnow, T.: Kaikoura tree theorems: Computing the maximum agreement subtree. Information Processing Letters\u00a048, 77\u201382 (1993)","journal-title":"Information Processing Letters"},{"key":"15_CR34","doi-asserted-by":"crossref","unstructured":"Thorley, J.L., Wilkinson, M.: A view of supertrees methods. In: Bioconsensus, DIMACS Amer. Math. Soc. Pub.,, vol.\u00a061, pp. 185\u2013194 (2003)","DOI":"10.1090\/dimacs\/061\/12"},{"key":"15_CR35","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1006\/jagm.1994.1018","volume":"16","author":"T.J. Warnow","year":"1994","unstructured":"Warnow, T.J.: Tree compatibility and inferring evolutionary history. Journal of Algorithms\u00a016, 388\u2013407 (1994)","journal-title":"Journal of Algorithms"},{"key":"15_CR36","unstructured":"Wilkinson, M., Thorley, J., Littlewood, D.T.J., Bray, R.A.: Interrelationships of the Platyhelminthes. In: Towards a phylogenetic supertree of Platyhelminthes, Taylor and Francis, London, vol.\u00a0ch.27 (2001)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27801-6_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:21:26Z","timestamp":1605741686000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27801-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223412","9783540278016"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27801-6_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}