{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:06:29Z","timestamp":1761620789106,"version":"3.41.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[1999,7,1]],"date-time":"1999-07-01T00:00:00Z","timestamp":930787200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1999,7,1]],"date-time":"1999-07-01T00:00:00Z","timestamp":930787200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Combinatorial Optimization"],"published-print":{"date-parts":[[1999,7]]},"DOI":"10.1023\/a:1009833626004","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T23:53:29Z","timestamp":1040601209000},"page":"183-197","source":"Crossref","is-referenced-by-count":43,"title":["On the Complexity of Constructing Evolutionary Trees"],"prefix":"10.1007","volume":"3","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","reference":[{"issue":"3","key":"211427_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, \u201cInferring a tree from lowest common ancestors with an application to the optimization of relational expressions,\u201d SIAM Journal of Computing, vol. 10, no. 3, pp. 405-421, 1981.","journal-title":"SIAM Journal of Computing"},{"doi-asserted-by":"crossref","unstructured":"M. Farach, T. Przytycka, and M. Thorup, \u201cComputing the agreement of trees with bounded degrees,\u201d in Proc. of the 3rd ESA, 1995, pp. 381-393.","key":"211427_CR2","DOI":"10.1007\/3-540-60313-1_157"},{"unstructured":"M. Farach and M. Thorup, \u201cFast comparison of evolutionary trees,\u201d in Proc. of the 5th ACM-SIAM SODA, 1994a, pp. 481-488.","key":"211427_CR3"},{"doi-asserted-by":"crossref","unstructured":"M. Farach and M. Thorup, \u201cOptimal evolutionary tree comparison by sparse dynamic programming,\u201d in Proc. of the 35th FOCS, 1994b, pp. 770-779.","key":"211427_CR4","DOI":"10.1109\/SFCS.1994.365716"},{"key":"211427_CR5","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, \u201cObtaining common pruned trees,\u201d Journal of Classification, vol. 2, pp. 255-276, 1985.","journal-title":"Journal of Classification"},{"key":"211427_CR6","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, \u201cNew \n$$\\frac{3}{4}$$\n-approximation algorithms for MAX SAT,\u201d SIAM Journal of Discrete Mathematics, vol. 7, pp. 656-666, 1994.","journal-title":"SIAM Journal of Discrete Mathematics"},{"doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, \u201cTesting of the long code and hardness for clique,\u201d in Proc. of the 28th ACM STOC, 1996, pp. 11-19.","key":"211427_CR7","DOI":"10.1145\/237814.237820"},{"key":"211427_CR8","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, \u201cOn the complexity of comparing evolutionary trees,\u201d Discrete Applied Mathematics, vol. 71, pp. 153-169, 1996.","journal-title":"Discrete Applied Mathematics"},{"unstructured":"M.R. Henzinger, V. King, and T. Warnow, \u201cConstructing a tree from homeomorphic subtrees, with applications to computational biology,\u201d in Proc. of the 7th ACM-SIAM SODA, 1996, pp. 333-340.","key":"211427_CR9"},{"volume-title":"Approximation Algorithms for NP-hard Problems","year":"1995","unstructured":"D.S. Hochbaum, Ed., Approximation Algorithms for NP-hard Problems, PWS Publishing Company: Boston, 1995.","key":"211427_CR10"},{"issue":"1","key":"211427_CR11","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, \u201cOn 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,\u201d SIAM Journal of Discrete Mathematics, vol. 2, no. 1, pp. 68-72, 1989.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"211427_CR12","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, \u201cApproximation algorithms for combinatorial problems,\u201d Journal of Computer and System Sciences, vol. 9, pp. 256-278, 1974.","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"S. Kannan, T.Warnow, and S. Yooseph, \u201cComputing the local consensus of trees,\u201d in Proc. of the 6th ACM-SIAM SODA, 1995, pp. 68-77.","key":"211427_CR13"},{"doi-asserted-by":"crossref","unstructured":"M.Y. Kao, T.W. Lam, T. Przytycka, W.K. Sung, and H.F. Ting, \u201cGeneral techniques for comparing unrooted evolutionary trees,\u201d in Proc. of the 29th ACM STOC, 1997, pp. 54-65.","key":"211427_CR14","DOI":"10.1145\/258533.258550"},{"doi-asserted-by":"crossref","unstructured":"D.R. Karger, \u201cMinimum cuts in near-linear time,\u201d in Proc. of the 28th ACM STOC, 1996, pp. 56-63.","key":"211427_CR15","DOI":"10.1145\/237814.237829"},{"doi-asserted-by":"crossref","unstructured":"D. Keselman and A. Amir, \u201cMaximum agreement subtree in a set of evolutionary trees-Metrics and efficient algorithms,\u201d in Proc. of the 35th FOCS, 1994, pp. 758-769.","key":"211427_CR16","DOI":"10.1109\/SFCS.1994.365717"},{"doi-asserted-by":"crossref","unstructured":"T.W. Lam, W.K. Sung, and H.F. Ting, \u201cComputing the unrooted maximum agreement subtree in sub-quadratic time,\u201d in Proc. of the 5th SWAT, 1996, pp. 124-135.","key":"211427_CR17","DOI":"10.1007\/3-540-61422-2_126"},{"key":"211427_CR18","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"C.H. Papadimitriou, \u201cComputational Complexity,\u201d Addison-Wesley: Reading, 1994."},{"doi-asserted-by":"crossref","unstructured":"C. Phillips and T.J.Warnow, \u201cThe asymmetric median tree-a new model for building consensus Trees,\u201d in Proc. of the 7th CPM, LNCS 1075, 1996, pp. 234-252.","key":"211427_CR19","DOI":"10.1007\/3-540-61258-0_18"},{"key":"211427_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, \u201cKaikoura tree theorems: Computing the maximum agreement subtree,\u201d Information Processing Letters, vol. 48, pp. 77-82, 1993.","journal-title":"Information Processing Letters"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009833626004.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009833626004\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009833626004.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:15:27Z","timestamp":1751282127000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009833626004"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,7]]},"references-count":20,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[1999,7]]}},"alternative-id":["211427"],"URL":"https:\/\/doi.org\/10.1023\/a:1009833626004","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[1999,7]]}}}