{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:44:24Z","timestamp":1767339864281},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540280613"},{"type":"electronic","value":"9783540318064"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11533719_14","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T09:34:13Z","timestamp":1127813653000},"page":"115-125","source":"Crossref","is-referenced-by-count":13,"title":["On the Approximation of Computing Evolutionary Trees"],"prefix":"10.1007","author":[{"given":"Vincent","family":"Berry","sequence":"first","affiliation":[]},{"given":"Sylvain","family":"Guillemot","sequence":"additional","affiliation":[]},{"given":"Fran\u00e7ois","family":"Nicolas","sequence":"additional","affiliation":[]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1\u20132","key":"14_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P. Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci.\u00a0237(1\u20132), 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"14_CR2","doi-asserted-by":"publisher","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 algorithm. SIAM J. on Comput.\u00a026(6), 1656\u20131669 (1997)","journal-title":"SIAM J. on Comput."},{"key":"14_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-540-27801-6_15","volume-title":"Combinatorial Pattern Matching","author":"V. Berry","year":"2004","unstructured":"Berry, V., Nicolas, F.: Maximum agreement and compatible supertrees. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 205\u2013219. Springer, Heidelberg (2004)"},{"key":"14_CR4","unstructured":"Berry, V., Nicolas, F.: Improved parametrized complexity of maximum agreement subtree and maximum compatible tree problems. IEEE Trans. on Comput. Biology and Bioinf. (to appear)"},{"issue":"4","key":"14_CR5","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1142\/S0129054100000363","volume":"11","author":"P. Bonizzoni","year":"2000","unstructured":"Bonizzoni, P., Della Vedova, G., Mauri, G.: Approximating the maximum isomorphic agreement subtree is hard. Int. J. of Found. of Comput. Sci.\u00a011(4), 579\u2013590 (2000)","journal-title":"Int. J. of Found. of Comput. Sci."},{"key":"14_CR6","unstructured":"Bryant, D.: Building trees, hunting for trees and comparing trees: theory and method in phylogenetic analysis. PhD thesis, University of Canterbury, Department of Mathemathics (1997)"},{"issue":"5","key":"14_CR7","doi-asserted-by":"publisher","first-page":"1385","DOI":"10.1137\/S0097539796313477","volume":"30","author":"R. Cole","year":"2001","unstructured":"Cole, R., Farach-Colton, M., Hariharan, R., Przytycka, T.M., Thorup, M.: An O(n log n) algorithm for the Maximum Agreement SubTree problem for binary trees. SIAM J. on Comput.\u00a030(5), 1385\u20131404 (2001)","journal-title":"SIAM J. on Comput."},{"key":"14_CR8","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/BF00276095","volume":"10","author":"G.F. Eastabrook","year":"1980","unstructured":"Eastabrook, G.F., McMorris, F.R.: When is one estimate of evolutionary relationships a refinement of another? J. of Math. Biol.\u00a010, 367\u2013373 (1980)","journal-title":"J. of Math. Biol."},{"issue":"1\u20133","key":"14_CR9","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1016\/S0304-3975(02)00535-2","volume":"299","author":"L. Engebretsen","year":"2003","unstructured":"Engebretsen, L., Holmerin, J.: Towards optimal lower bounds for clique and chromatic number. Theor. Comput. Sci.\u00a0299(1\u20133), 537\u2013584 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"14_CR10","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.M., Thorup, M.: On the agreement of many trees. Inf. Proces. Letters\u00a055(6), 297\u2013301 (1995)","journal-title":"Inf. Proces. Letters"},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/3-540-45753-4_12","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"G. Ganapathy","year":"2002","unstructured":"Ganapathy, G., Warnow, T.J.: Approximating the complement of the maximum compatible subset of leaves of k trees. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, pp. 122\u2013134. Springer, Heidelberg (2002)"},{"key":"14_CR12","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.J.: 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)"},{"issue":"2","key":"14_CR13","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/PL00009212","volume":"21","author":"A. Gupta","year":"1998","unstructured":"Gupta, A., Nishimura, N.: Finding largest subtrees and smallest supertrees. Algorithmica\u00a021(2), 183\u2013210 (1998)","journal-title":"Algorithmica"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Halld\u00f2rsson, M.M.: Approximations of weighted independent set and hereditary subset problems. J. of Graph Algor. and Appl.\u00a04(1) (2000)","DOI":"10.7155\/jgaa.00020"},{"issue":"2","key":"14_CR15","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. Letters\u00a09(2), 55\u201359 (1996)","journal-title":"Appl. Math. Letters"},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n1\u2212\u03b5. Acta Math.\u00a0182, 105\u2013142 (1999)","journal-title":"Acta Math."},{"issue":"1\u20133","key":"14_CR17","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(1\u20133), 153\u2013169 (1996)","journal-title":"Disc. Appl. Math."},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/978-3-540-24698-5_53","volume-title":"LATIN 2004: Theoretical Informatics","author":"J. Jansson","year":"2004","unstructured":"Jansson, J., Ng, J.H.-K., Sadakane, K., Sung, W.-K.: Rooted maximum agreement supertrees. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol.\u00a02976, pp. 499\u2013508. Springer, Heidelberg (2004)"},{"issue":"5","key":"14_CR19","doi-asserted-by":"publisher","first-page":"1122","DOI":"10.1137\/S009753979223842X","volume":"24","author":"T. Jiang","year":"1995","unstructured":"Jiang, T., Li, M.: On the approximation of shortest common supersequences and longest common subsequences. SIAM J. on Comput.\u00a024(5), 1122\u20131139 (1995)","journal-title":"SIAM J. on Comput."},{"key":"14_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1007\/3-540-48481-7_38","volume-title":"Algorithms - ESA\u201999","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: Ne\u0161et\u0159il, J. (ed.) ESA 1999. LNCS, vol.\u00a01643, pp. 438\u2013449. Springer, Heidelberg (1999)"},{"issue":"2","key":"14_CR21","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 Algor.\u00a040(2), 212\u2013233 (2001)","journal-title":"J. of Algor."},{"issue":"2","key":"14_CR22","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.J.: Kaikoura tree theorems: Computing the maximum agreement subtree. Inf. Proces. Letters\u00a048(2), 77\u201382 (1993)","journal-title":"Inf. Proces. Letters"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11533719_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,25]],"date-time":"2019-03-25T22:50:48Z","timestamp":1553554248000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11533719_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540280613","9783540318064"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11533719_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}