{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:27:49Z","timestamp":1751282869379},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614227"},{"type":"electronic","value":"9783540685296"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_126","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:36:58Z","timestamp":1330292218000},"page":"124-135","source":"Crossref","is-referenced-by-count":3,"title":["Computing the unrooted maximum agreement subtree in sub-quadratic time"],"prefix":"10.1007","author":[{"given":"T. W.","family":"Lam","sequence":"first","affiliation":[]},{"given":"W. K.","family":"Sung","sequence":"additional","affiliation":[]},{"given":"H. F.","family":"Ting","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"R. Agarwala and D. Fernandez-Baca, A polynomial-time algorithm for the phylogeny problem when the number of character states is fixed, FOCS, 140\u2013147, 1993.","DOI":"10.1109\/SFCS.1993.366873"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"H. Bodlaender, M. Fellows and T. Warnow, Two strikes against perfect phylogeny, ICALP, 273\u2013283, 1992.","DOI":"10.1007\/3-540-55719-9_80"},{"key":"12_CR3","unstructured":"R. Cole and R. Hariharan, An O(n log n) algorithm for the maximum agreement subtree problem for binary trees, SODA, 323\u2013332, 1996."},{"issue":"4","key":"12_CR4","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/BF02458863","volume":"49","author":"W.H.E. Day","year":"1987","unstructured":"W.H.E. Day, Computational complexity of inferring phylogenies from dissimilarity matrices, Bulletin of Mathematical Biology, 49(4):461\u2013467, 1987.","journal-title":"Bulletin of Mathematical Biology"},{"key":"12_CR5","unstructured":"M. Farach and M. Thorup, Fast comparison of evolutionary trees, SODA, 481\u2013488, 1994."},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"M. Farach and M. Thorup, Optimal evolutionary tree comparison by sparse dynamic programming, FOCS, 770\u2013779, 1994.","DOI":"10.1109\/SFCS.1994.365716"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"M. Farach, T. Przytycka and M. Thorup, Computing the agreement of trees with bounded degrees, ESA, 381\u2013393, 1995.","DOI":"10.1007\/3-540-60313-1_157"},{"issue":"4","key":"12_CR8","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1086\/412935","volume":"57","author":"J. Felsenstein","year":"1982","unstructured":"J. Felsenstein, Numerical methods for inferring evolutionary tree, The Quarterly Review of Biology, 57(4):379\u2013404, 1982.","journal-title":"The Quarterly Review of Biology"},{"key":"12_CR9","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01908078","volume":"2","author":"C. Finden","year":"1985","unstructured":"C. Finden and A. Gordon, Obtaining common pruned trees, Journal of Classification, 2:255\u2013276, 1985.","journal-title":"Journal of Classification"},{"issue":"5","key":"12_CR10","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"H. Gabow","year":"1989","unstructured":"H. Gabow and R. Tarjan, Faster scaling algorithms for network problems, SIAM Journal of Computing, 18(5): 1013\u20131036, 1989.","journal-title":"SIAM Journal of Computing"},{"key":"12_CR11","unstructured":"S. Kannan, T. Warnow and S. Yooseph, Computing the local consensus of trees, SODA, 68\u201377, 1995."},{"key":"12_CR12","unstructured":"J. Kececioglu and D. Gusfield, Reconstructing a history of recombinations from a set of sequences, SODA, 471\u2013480, 1994."},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"D. Keselman and A. Amir, Maximum agreement subtree in a set of evolutionary trees \u2014 Metrics and efficient algorithms, FOCS, 758\u2013769, 1994.","DOI":"10.1109\/SFCS.1994.365717"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"E. Kubicka, G. Kubicki and F. McMorris, An algorithm to find agreement subtrees, Journal of Classification, 1994.","DOI":"10.1007\/BF01202269"},{"key":"12_CR15","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0020-0190(93)90181-8","volume":"48","author":"M. Steel","year":"1994","unstructured":"M. Steel and T. Warnow, Kaikoura tree theorems: computing the maximum agreement subtree, Information Processing Letters, 48:77\u201382, 1994.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_126.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:05:58Z","timestamp":1605647158000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_126"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_126","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}