{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:18:01Z","timestamp":1725459481059},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633570"},{"type":"electronic","value":"9783540695226"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0045080","type":"book-chapter","created":{"date-parts":[[2006,2,6]],"date-time":"2006-02-06T14:16:11Z","timestamp":1139235371000},"page":"134-145","source":"Crossref","is-referenced-by-count":2,"title":["On the complexity of computing evolutionary trees"],"prefix":"10.1007","author":[{"given":"Leszek","family":"Gasieniec","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper","family":"Jansson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"\u00d6stlin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,1,24]]},"reference":[{"issue":"3","key":"15_CR1","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"A.V. Aho","year":"1981","unstructured":"A.V. Aho, Y. Sagiv, T.G. Szymanski, and J.D. Ullman. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal of Computing, Vol. 10, No. 3, 1981, pp. 405\u2013421.","journal-title":"SIAM Journal of Computing"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"M. Bellare and M. Sudan. Improved non-approximability results. Proc. of the 26th ACM STOC, 1994, pp. 184\u2013193.","DOI":"10.1145\/195058.195129"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"M. Farach, T. Przytycka, and M. Thorup. Computing the agreement of trees with bounded degrees. Proc. of the 3rd ESA, 1995, pp. 381\u2013393.","DOI":"10.1007\/3-540-60313-1_157"},{"key":"15_CR4","unstructured":"M. Farach and M. Thorup. Fast Comparison of Evolutionary Trees. Proc. of the 5th ACM-SIAM SODA, 1994, pp. 481\u2013488."},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"M. Farach and M. Thorup. Optimal evolutionary tree comparison by sparse dynamic programming. Proc. of the 35th FOGS, 1994, pp. 770\u2013779.","DOI":"10.1109\/SFCS.1994.365716"},{"key":"15_CR6","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01908078","volume":"2","author":"C.R. Finden","year":"1985","unstructured":"C.R. Finden and A.D. Gordon. Obtaining common pruned trees. Journal of Classification 2, 1985, pp. 255\u2013276.","journal-title":"Journal of Classification"},{"key":"15_CR7","unstructured":"L. Gasieniec, J. Jansson, A. Lingas, and A. \u00d6stlin. On the complexity of computing evolutionary trees. Technical Report MPI-I-96-1-031, Max-Planck Institut f\u00fcr Informatik, Saarbr\u00fccken, November 1996."},{"key":"15_CR8","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"M.X. Goemans","year":"1994","unstructured":"M.X. Goemans and D.P. Williamson. New 3\/4-approximation algorithms for MAX SAT. SIAM Journal of Discrete Mathematics, 7, 1994, pp. 656\u2013666.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0166-218X(96)00062-5","volume":"71","author":"J. Hein","year":"1996","unstructured":"J. Hein, T. Jiang, L. Wang, and K. Zhang. On the Complexity of Comparing Evolutionary Trees. Discrete Applied Mathematics, 71, 1996, pp. 153\u2013169.","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR10","unstructured":"M.R. Henzinger, V. King, and T. Warnow. Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Biology. Proc. of the 7th ACM-SIAM SODA, 1996, pp. 333\u2013340."},{"volume-title":"Approximation Algorithms for NP-hard Problems","year":"1995","key":"15_CR11","unstructured":"D.S. Hochbaum (editor). Approximation Algorithms for NP-hard Problems. PWS Publishing Company, Boston, 1995."},{"issue":"1","key":"15_CR12","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"C.A.J. Hurkens","year":"1989","unstructured":"C.A.J. Hurkens and A. Schrijver. On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM Journal of Discrete Mathematics, Vol. 2, No. 1, 1989, pp. 68\u201372.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"15_CR13","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"D.S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9, 1974, pp. 256\u2013278.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR14","unstructured":"S. Kannan, T. Warnow, and S. Yooseph. Computing the Local Consensus of Trees. Proc. of the 6th ACM-SIAM SODA, 1995, pp. 68\u201377."},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"D.R. Karger. Minimum Cuts in Near-Linear Time. Proc. of the 28th ACM STOC, 1996, pp. 56\u201363.","DOI":"10.1145\/237814.237829"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"D. Keselman and A. Amir. Maximum agreement subtree in a set of evolutionary trees \u2014 Metrics and efficient algorithms. Proc. of the 35th FOCS, 1994, pp. 758\u2013769.","DOI":"10.1109\/SFCS.1994.365717"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"T.W. Lam, W.K. Sung, and H.F. Ting. Computing the Unrooted Maximum Agreement Subtree in Sub-quadratic Time. Proc. of the 5th SWAT, 1996, pp. 124\u2013135.","DOI":"10.1007\/3-540-61422-2_126"},{"key":"15_CR18","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"C.H. Papadimitriou. Computational Complexity, Addison-Wesley, Reading, 1994."},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"C. Phillips and T.J. Warnow. The Asymmetric Median Tree \u2014 A New Model for Building Consensus Trees. Proc. of the 7th CPM, LNCS 1075, 1996, pp. 234\u2013252.","DOI":"10.1007\/3-540-61258-0_18"},{"key":"15_CR20","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0020-0190(93)90181-8","volume":"48","author":"M. Steel","year":"1993","unstructured":"M. Steel and T. Warnow. Kaikoura tree theorems: Computing the maximum agreement subtree. Information Processing Letters 48, 1993, pp. 77\u201382.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0045080","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T19:17:33Z","timestamp":1555442253000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0045080"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633570","9783540695226"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0045080","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}