{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T02:17:02Z","timestamp":1743041822510,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319199283"},{"type":"electronic","value":"9783319199290"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19929-0_23","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T13:09:49Z","timestamp":1434373789000},"page":"272-283","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets"],"prefix":"10.1007","author":[{"given":"Jesper","family":"Jansson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eva-Marta","family":"Lundell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"issue":"3","key":"23_CR1","doi-asserted-by":"publisher","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."},{"issue":"1","key":"23_CR2","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1006\/jcss.1998.1605","volume":"58","author":"S Arora","year":"1999","unstructured":"Arora, S., Karger, D., Karpinski, M.: Polynomial time approximation schemes for dense instances of $${NP}$$-hard problems. J. Comput. Syst. Sci. 58(1), 193\u2013210 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR3","unstructured":"Bryant, D.: Building Trees, Hunting for Trees, and Comparing Trees: Theory and Methods in Phylogenetic Analysis. Ph.D. thesis. University of Canterbury, Christchurch, New Zealand (1997)"},{"issue":"1","key":"23_CR4","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.jda.2009.01.004","volume":"8","author":"J Byrka","year":"2010","unstructured":"Byrka, J., Gawrychowski, P., Huber, K.T., Kelk, S.: Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks. J. Discrete Algorithms 8(1), 65\u201375 (2010)","journal-title":"J. Discrete Algorithms"},{"issue":"11","key":"23_CR5","doi-asserted-by":"publisher","first-page":"1136","DOI":"10.1016\/j.dam.2010.03.004","volume":"158","author":"J Byrka","year":"2010","unstructured":"Byrka, J., Guillemot, S., Jansson, J.: New results on optimizing rooted triplets consistency. Discrete Appl. Math. 158(11), 1136\u20131147 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"6\u20137","key":"23_CR6","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1016\/j.dam.2005.05.043","volume":"155","author":"B Chor","year":"2007","unstructured":"Chor, B., Hendy, M., Penny, D.: Analytic solutions for three taxon ML trees with variable rates across sites. Discrete Appl. Math. 155(6\u20137), 750\u2013758 (2007)","journal-title":"Discrete Appl. Math."},{"key":"23_CR7","volume-title":"Inferring Phylogenies","author":"J Felsenstein","year":"2004","unstructured":"Felsenstein, J.: Inferring Phylogenies. Sinauer Associates Inc., Sunderland (2004)"},{"issue":"2\u20133","key":"23_CR8","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1023\/A:1009833626004","volume":"3","author":"L Ga\u0327sieniec","year":"1999","unstructured":"Ga\u0327sieniec, L., Jansson, J., Lingas, A., \u00d6stlin, A.: On the complexity of constructing evolutionary trees. J. Comb. Optim. 3(2\u20133), 183\u2013197 (1999)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"23_CR9","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1142\/S0219720006001709","volume":"4","author":"YJ He","year":"2006","unstructured":"He, Y.J., Huynh, T.N.D., Jansson, J., Sung, W.-K.: Inferring phylogenetic relationships avoiding forbidden rooted triplets. J. Bioinform. Comput. Biol. 4(1), 59\u201374 (2006)","journal-title":"J. Bioinform. Comput. Biol."},{"issue":"1","key":"23_CR10","doi-asserted-by":"publisher","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), 1\u201313 (1999)","journal-title":"Algorithmica"},{"issue":"4","key":"23_CR11","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1142\/S0219720009004308","volume":"7","author":"L van Iersel","year":"2009","unstructured":"van Iersel, L., Kelk, S., Mnich, M.: Uniqueness, intractability and exact algorithms: reflections on level-$$k$$ phylogenetic networks. J. Bioinform. Comput. Biol. 7(4), 597\u2013623 (2009)","journal-title":"J. Bioinform. Comput. Biol."},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Jansson, J.: On the complexity of inferring rooted evolutionary trees. In: Proceedings of the Brazilian Symposium on Graphs, Algorithms, and Combinatorics (GRACO 2001). Electronic Notes in Discrete Mathematics, vol. 7, pp. 50\u201353. Elsevier (2001)","DOI":"10.1016\/S1571-0653(04)00222-7"},{"key":"23_CR13","unstructured":"Jansson, J., Lingas, A., Lundell, E.-M.: A triplet approach to approximations of evolutionary trees. Poster H15 presented at RECOMB 2004 (2004)"},{"issue":"6","key":"23_CR14","doi-asserted-by":"publisher","first-page":"1942","DOI":"10.1137\/S0097539799361683","volume":"30","author":"T Jiang","year":"2001","unstructured":"Jiang, T., Kearney, P., Li, M.: A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application. SIAM J. Comput. 30(6), 1942\u20131961 (2001)","journal-title":"SIAM J. Comput."},{"key":"23_CR15","first-page":"111","volume-title":"Current Topics in Computational Molecular Biology","author":"P Kearney","year":"2002","unstructured":"Kearney, P.: Phylogenetics and the quartet method. In: Jiang, T., Xu, Y., Zhang, M.Q. (eds.) Current Topics in Computational Molecular Biology, pp. 111\u2013133. The MIT Press, Massachusetts (2002)"},{"issue":"4","key":"23_CR16","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1109\/TCBB.2006.58","volume":"3","author":"S Snir","year":"2006","unstructured":"Snir, S., Rao, S.: Using max cut to enhance rooted trees consistency. IEEE\/ACM Trans. Comput. Biol. Bioinf. 3(4), 323\u2013333 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"issue":"1","key":"23_CR17","doi-asserted-by":"publisher","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":"23_CR18","first-page":"181","volume":"20","author":"BY Wu","year":"2004","unstructured":"Wu, B.Y.: Constructing evolutionary trees from rooted triplets. J. Inf. Sci. Eng. 20, 181\u2013190 (2004)","journal-title":"J. Inf. Sci. Eng."},{"issue":"1","key":"23_CR19","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1023\/B:JOCO.0000021936.04215.68","volume":"8","author":"BY Wu","year":"2004","unstructured":"Wu, B.Y.: Constructing the maximum consensus tree from rooted triples. J. Comb. Optim. 8(1), 29\u201339 (2004)","journal-title":"J. Comb. Optim."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19929-0_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T01:30:58Z","timestamp":1676943058000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19929-0_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319199283","9783319199290"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19929-0_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}