{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:40:49Z","timestamp":1777596049484,"version":"3.51.4"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T00:00:00Z","timestamp":1446422400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61420106009"],"award-info":[{"award-number":["61420106009"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China (CN)","doi-asserted-by":"publisher","award":["61232001"],"award-info":[{"award-number":["61232001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,12]]},"DOI":"10.1007\/s00453-015-0087-6","type":"journal-article","created":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T10:11:18Z","timestamp":1446459078000},"page":"867-889","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Approximating Maximum Agreement Forest on Multiple Binary Trees"],"prefix":"10.1007","volume":"76","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feng","family":"Shi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,2]]},"reference":[{"key":"87_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A Aho","year":"1974","unstructured":"Aho, A., Hopcroft, J., Ullman, J.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)"},{"issue":"1","key":"87_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00026-001-8006-8","volume":"5","author":"B Allen","year":"2001","unstructured":"Allen, B., Steel, M.: Subtree transfer operations and their induced metrics on evolutionary trees. Ann. Comb. 5(1), 1\u201315 (2001)","journal-title":"Ann. Comb."},{"issue":"1","key":"87_CR3","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1186\/1471-2148-6-15","volume":"6","author":"RG Beiko","year":"2006","unstructured":"Beiko, R.G., Hamilton, N.: Phylogenetic identification of lateral genetic transfer events. BMC Evolut. Biol. 6(1), 15 (2006)","journal-title":"BMC Evolut. Biol."},{"issue":"8","key":"87_CR4","doi-asserted-by":"crossref","first-page":"1419","DOI":"10.1089\/cmb.2006.13.1419","volume":"13","author":"M Bonet","year":"2006","unstructured":"Bonet, M., John, K.S., Mahindru, R., Amenta, N.: Approximating subtree distances between phylogenies. J. Comput. Biol. 13(8), 1419\u20131434 (2006)","journal-title":"J. Comput. Biol."},{"issue":"3","key":"87_CR5","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1016\/j.jda.2007.10.002","volume":"6","author":"M Bordewich","year":"2008","unstructured":"Bordewich, M., McCartin, C., Semple, C.: A 3-approximation algorithm for the subtree distance between phylogenies. J. Discrete Algorithms 6(3), 458\u2013471 (2008)","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"87_CR6","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/s00026-004-0229-z","volume":"8","author":"M Bordewich","year":"2005","unstructured":"Bordewich, M., Semple, C.: On the computational complexity of the rooted subtree prune and regraft distance. Ann. Comb. 8(4), 409\u2013423 (2005)","journal-title":"Ann. Comb."},{"key":"87_CR7","first-page":"387","volume-title":"Mathematics in the Archaeological and Historical Sciences","author":"P Buneman","year":"1971","unstructured":"Buneman, P.: The recovery of trees from measures of dissimilarity. In: Kendall, D., Tauta, P. (eds.) Mathematics in the Archaeological and Historical Sciences, pp. 387\u2013395. Edinburgh University Press, Edinburgh (1971)"},{"key":"87_CR8","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/j.ipl.2004.11.004","volume":"93","author":"F Chataigner","year":"2005","unstructured":"Chataigner, F.: Approximating the maximum agreement forest on $$k$$ k trees. Inf. Process. Lett. 93, 239\u2013244 (2005)","journal-title":"Inf. Process. Lett."},{"key":"87_CR9","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1016\/j.tcs.2014.10.031","volume":"562","author":"J Chen","year":"2015","unstructured":"Chen, J., Fan, J.-H., Sze, S.-H.: Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees. Theor. Comput. Sci. 562, 496\u2013512 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"87_CR10","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1109\/TCBB.2011.137","volume":"9","author":"Z Chen","year":"2012","unstructured":"Chen, Z., Wang, L.: Algorithms for reticulate networks of multiple phylogenetic trees. IEEE\/ACM Trans. Comput. Biol. Bioinform. 9, 372\u2013384 (2012)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"87_CR11","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th edition. Graduate Texts in Mathematics, vol. 173. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-14279-6"},{"issue":"1","key":"87_CR12","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1093\/molbev\/msu287","volume":"32","author":"G Dudas","year":"2014","unstructured":"Dudas, G., Bedford, T., Lycett, S., Rambaut, A.: Reassortment between influenza B lineages and the emergence of a coadapted PB1-PB2-HA gene complex. Mol. Biol. Evol. 32(1), 162\u2013172 (2014). (supplemental information)","journal-title":"Mol. Biol. Evol."},{"issue":"3","key":"87_CR13","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1007\/s00224-007-1329-z","volume":"41","author":"M Hallett","year":"2007","unstructured":"Hallett, M., McCartin, C.: A faster FPT algorithm for the maximum agreement forest problem. Theory Comput. Syst. 41(3), 539\u2013550 (2007)","journal-title":"Theory Comput. Syst."},{"key":"87_CR14","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."},{"issue":"4","key":"87_CR15","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1006\/jtbi.1996.0188","volume":"182","author":"M Li","year":"1996","unstructured":"Li, M., Tromp, J., Zhang, L.: On the nearest neighbour interchange distance between evolutionary trees. J. Theor. Biol. 182(4), 463\u2013467 (1996)","journal-title":"J. Theor. Biol."},{"key":"87_CR16","unstructured":"Mukhopadhyay, A., Bhabak, P.: A 3-factor approximation algorithm for a minimum acyclic agreement forest on $$k$$ k rooted, binary phylogenetic trees. CoRR abs\/1407.7125 (2014)"},{"issue":"1\u20132","key":"87_CR17","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","volume":"53","author":"D Robinson","year":"1981","unstructured":"Robinson, D., Foulds, L.: Comparison of phylogenetic trees. Math. Biosci. 53(1\u20132), 131\u2013147 (1981)","journal-title":"Math. Biosci."},{"key":"87_CR18","doi-asserted-by":"crossref","unstructured":"Rodrigues, M., Sagot, M., Wakabayashi, Y.: Some approximation results for the maximum agreement forest problem. In: Proceedigs of the RANDOM-APPROX 2001, Lecture Notes in Computer Science, vol. 2129, pp. 159\u2013169 (2001)","DOI":"10.1007\/3-540-44666-4_19"},{"key":"87_CR19","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.tcs.2006.12.011","volume":"374","author":"E Rodrigues","year":"2007","unstructured":"Rodrigues, E., Sagot, M., Wakabayashi, Y.: The maximum agreement forest problem: approximation algorithms and computational experiments. Theor. Comput. Sci. 374, 91\u2013110 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"87_CR20","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.tcs.2013.12.025","volume":"554","author":"F Shi","year":"2014","unstructured":"Shi, F., Wang, J., Chen, J., Feng, Q., Guo, J.: Algorithms for parameterized maximum agreement forest problem on multiple trees. Theor. Comput. Sci. 554, 207\u2013216 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"87_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-015-9921-7","author":"F Shi","year":"2015","unstructured":"Shi, F., Feng, Q., You, J., Wang, J.: Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees. J. Comb. Optim. (2015a). doi: 10.1007\/s10878-015-9921-7","journal-title":"J. Comb. Optim."},{"key":"87_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-015-5355-1","author":"F Shi","year":"2015","unstructured":"Shi, F., Wang, J., Yang, Y., Feng, Q., Li, W., Chen, J.: A fixed-parameter algorithm for the maximum agreement forset problem on multifurcating trees. Sci. China Inf. Sci. (2015b). doi: 10.1007\/s11432-015-5355-1","journal-title":"Sci. China Inf. Sci."},{"key":"87_CR23","first-page":"407","volume-title":"Molecular Systematics","author":"D Swofford","year":"1996","unstructured":"Swofford, D., Olsen, G., Waddell, P., Hillis, D.: Phylogenetic inference. In: Hillis, D., Moritz, D., Mable, B. (eds.) Molecular Systematics, 2nd edn, pp. 407\u2013514. Sinauer Associates, Sunderiand (1996)","edition":"2"},{"key":"87_CR24","doi-asserted-by":"crossref","unstructured":"Whidden, C., Zeh, N.: A unifying view on approximation and FPT of agreement forests. In: Proceedings of the WABI 2009, Lecture Notes in Computer Science, vol.\u00a05724, pp.\u00a0390\u2013401 (2009)","DOI":"10.1007\/978-3-642-04241-6_32"},{"issue":"4","key":"87_CR25","doi-asserted-by":"crossref","first-page":"1431","DOI":"10.1137\/110845045","volume":"42","author":"C Whidden","year":"2013","unstructured":"Whidden, C., Beiko, R.G., Zeh, N.: Fixed-parameter algorithms for maximum agreement forests. SIAM J. Comput. 42(4), 1431\u20131466 (2013)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"87_CR26","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1093\/sysbio\/syu023","volume":"63","author":"C Whidden","year":"2014","unstructured":"Whidden, C., Zeh, N., Beiko, R.G.: Supertrees based on the subtree prune-and-regraft distance. Syst. Biol. 63(4), 566\u2013581 (2014)","journal-title":"Syst. Biol."},{"issue":"3","key":"87_CR27","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1093\/sysbio\/syv006","volume":"64","author":"C Whidden","year":"2015","unstructured":"Whidden, C., Matsen IV, F.A.: Quantifying MCMC exploration of phylogenetic tree space. Syst. Biol. 64(3), 472 (2015)","journal-title":"Syst. Biol."},{"issue":"12","key":"87_CR28","doi-asserted-by":"crossref","first-page":"i140","DOI":"10.1093\/bioinformatics\/btq198","volume":"26","author":"Y Wu","year":"2010","unstructured":"Wu, Y.: Close lower and upper bounds for the minimum reticulate network of multiple phylogenetic trees. Bioinformatics 26(12), i140\u2013i148 (2010)","journal-title":"Bioinformatics"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0087-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0087-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0087-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0087-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:22Z","timestamp":1559072842000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0087-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,2]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["87"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0087-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,2]]}}}