{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T07:35:12Z","timestamp":1725521712798},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540921813"},{"type":"electronic","value":"9783540921820"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-92182-0_44","type":"book-chapter","created":{"date-parts":[[2008,12,9]],"date-time":"2008-12-09T21:38:06Z","timestamp":1228858686000},"page":"484-495","source":"Crossref","is-referenced-by-count":4,"title":["New Results on Optimizing Rooted Triplets Consistency"],"prefix":"10.1007","author":[{"given":"Jaroslaw","family":"Byrka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sylvain","family":"Guillemot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper","family":"Jansson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"44_CR1","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"A.V. 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 Journal on Computing\u00a010(3), 405\u2013421 (1981)","journal-title":"SIAM Journal on Computing"},{"issue":"8","key":"44_CR2","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1016\/j.ic.2007.02.006","volume":"205","author":"N. Ailon","year":"2007","unstructured":"Ailon, N., Alon, N.: Hardness of fully dense problems. Information and Computation\u00a0205(8), 1117\u20131129 (2007)","journal-title":"Information and Computation"},{"issue":"1","key":"44_CR3","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1137\/050623905","volume":"20","author":"N. Alon","year":"2006","unstructured":"Alon, N.: Ranking Tournaments. SIAM Journal of Discrete Mathematics\u00a020(1), 137\u2013142 (2006)","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"44_CR4","unstructured":"Bryant, D.: Building Trees, Hunting for Trees, and Comparing Trees: Theory and Methods in Phylogenetic Analysis. PhD thesis, University of Canterbury, Christchurch, New Zealand (1997)"},{"key":"44_CR5","unstructured":"Byrka, J., Gawrychowski, P., Huber, K.T., Kelk, S.: Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks (submitted, 2008)"},{"issue":"4","key":"44_CR6","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A Threshold of ln n for Approximating Set Cover. Journal of the ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"Journal of the ACM"},{"key":"44_CR7","unstructured":"Felsenstein, J.: Inferring Phylogenies. Sinauer Associates, Inc. (2004)"},{"key":"44_CR8","series-title":"Australian Computer Science Communications","first-page":"67","volume-title":"Proc. of CATS 1998","author":"L. Ga\u0327sieniec","year":"1998","unstructured":"Ga\u0327sieniec, L., Jansson, J., Lingas, A., \u00d6stlin, A.: Inferring ordered trees from local constraints. In: Proc. of CATS 1998. Australian Computer Science Communications, vol.\u00a020(3), pp. 67\u201376. Springer, Singapore (1998)"},{"issue":"2\u20133","key":"44_CR9","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. Journal of Combinatorial Optimization\u00a03(2\u20133), 183\u2013197 (1999)","journal-title":"Journal of Combinatorial Optimization"},{"issue":"1","key":"44_CR10","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1142\/S0219720006001709","volume":"4","author":"Y.J. He","year":"2006","unstructured":"He, Y.J., Huynh, T.N.D., Jansson, J., Sung, W.-K.: Inferring phylogenetic relationships avoiding forbidden rooted triplets. Journal of Bioinformatics and Computational Biology\u00a04(1), 59\u201374 (2006)","journal-title":"Journal of Bioinformatics and Computational Biology"},{"issue":"1","key":"44_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00009268","volume":"24","author":"M.R. Henzinger","year":"1999","unstructured":"Henzinger, M.R., King, V., Warnow, T.: Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica\u00a024(1), 1\u201313 (1999)","journal-title":"Algorithmica"},{"issue":"4","key":"44_CR12","doi-asserted-by":"publisher","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. Journal of the ACM\u00a048(4), 723\u2013760 (2001)","journal-title":"Journal of the ACM"},{"key":"44_CR13","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1007\/978-3-540-78839-3_40","volume-title":"Research in Computational Molecular Biology","author":"L. Iersel van","year":"2008","unstructured":"van Iersel, L., Keijsper, J., Kelk, S., Stougie, L., Hagen, F., Boekhout, T.: Constructing level-2 phylogenetic networks from triplets. In: Vingron, M., Wong, L. (eds.) RECOMB 2008. LNCS (LNBI), vol.\u00a04955, pp. 450\u2013462. Springer, Heidelberg (2008)"},{"key":"44_CR14","doi-asserted-by":"crossref","unstructured":"van Iersel, L., Kelk, S., Mnich, M.: Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks (submitted, 2008)","DOI":"10.1142\/S0219720009004308"},{"key":"44_CR15","series-title":"Electronic Notes in Discrete Mathematics","first-page":"121","volume-title":"Proc. of GRACO\u00a02001","author":"J. Jansson","year":"2001","unstructured":"Jansson, J.: On the complexity of inferring rooted evolutionary trees. In: Proc. of GRACO\u00a02001. Electronic Notes in Discrete Mathematics, vol.\u00a07, pp. 121\u2013125. Elsevier, Amsterdam (2001)"},{"key":"44_CR16","unstructured":"Jansson, J., Lingas, A., Lundell, E.-M.: A triplet approach to approximations of evolutionary trees. In: Poster\u00a0H15 presented at RECOMB\u00a02004 (2004)"},{"issue":"4","key":"44_CR17","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00453-004-1147-5","volume":"43","author":"J. Jansson","year":"2005","unstructured":"Jansson, J., Ng, J.H.-K., Sadakane, K., Sung, W.-K.: Rooted maximum agreement supertrees. Algorithmica\u00a043(4), 293\u2013307 (2005)","journal-title":"Algorithmica"},{"issue":"5","key":"44_CR18","doi-asserted-by":"publisher","first-page":"1098","DOI":"10.1137\/S0097539704446529","volume":"35","author":"J. Jansson","year":"2006","unstructured":"Jansson, J., Nguyen, N.B., Sung, W.-K.: Algorithms for combining rooted triplets into a galled phylogenetic network. SIAM Journal on Computing\u00a035(5), 1098\u20131121 (2006)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"44_CR19","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.tcs.2006.06.022","volume":"363","author":"J. Jansson","year":"2006","unstructured":"Jansson, J., Sung, W.-K.: Inferring a level-1 phylogenetic network from a dense set of rooted triplets. Theoretical Computer Science\u00a0363(1), 60\u201368 (2006)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"44_CR20","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 Journal on Computing\u00a030(6), 1942\u20131961 (2001)","journal-title":"SIAM Journal on Computing"},{"issue":"1\u20132","key":"44_CR21","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0166-218X(95)00074-2","volume":"69","author":"M.P. Ng","year":"1996","unstructured":"Ng, M.P., Wormald, N.C.: Reconstruction of rooted trees from subtrees. Discrete Applied Mathematics\u00a069(1\u20132), 19\u201331 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"44_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/3-540-45784-4_41","volume-title":"Algorithms in Bioinformatics","author":"R.D.M. Page","year":"2002","unstructured":"Page, R.D.M.: Modified mincut supertrees. In: Guig\u00f3, R., Gusfield, D. (eds.) WABI 2002. LNCS, vol.\u00a02452, pp. 537\u2013552. Springer, Heidelberg (2002)"},{"issue":"1\u20133","key":"44_CR23","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 supertree method for rooted trees. Discrete Applied Mathematics\u00a0105(1\u20133), 147\u2013158 (2000)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"44_CR24","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 Transactions on Computational Biology and Bioinformatics\u00a03(4), 323\u2013333 (2006)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"issue":"1","key":"44_CR25","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1023\/B:JOCO.0000021936.04215.68","volume":"8","author":"B.Y. Wu","year":"2004","unstructured":"Wu, B.Y.: Constructing the maximum consensus tree from rooted triples. Journal of Combinatorial Optimization\u00a08(1), 29\u201339 (2004)","journal-title":"Journal of Combinatorial Optimization"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92182-0_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T23:44:14Z","timestamp":1557963854000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92182-0_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540921813","9783540921820"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92182-0_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}