{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:09:01Z","timestamp":1725664141909},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540600442"},{"type":"electronic","value":"9783540494126"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60044-2_42","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:35:18Z","timestamp":1330277718000},"page":"177-190","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the complexity of comparing evolutionary trees"],"prefix":"10.1007","author":[{"given":"Jotun","family":"Hein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lusheng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kaizhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"13_CR1","unstructured":"A. Amir and D. Keselman, Maximum agreement subtree in a set of evolutionary trees \u2014 metrics and efficient algorithms, IEEE FOCS'94, 1994."},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems, Proc. 33rd IEEE Symp. Found. Comp. Sci., 14\u201323, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0025-5564(76)90035-3","volume":"29","author":"G. Estabrook","year":"1976","unstructured":"G. Estabrook, C. Johnson and F. McMorris, A mathematical foundation for the analysis of cladistic character compatibility, Math. Biosci. 29, 181\u2013187, 1976.","journal-title":"Math. Biosci."},{"key":"13_CR4","unstructured":"M. Farach and M. Thorup, Fast comparison of evolutionary trees, in Proc. 5ith Annual ACM-SIAM Symposium on Discrete Algorithms, 1994."},{"key":"13_CR5","unstructured":"M. Farach and M. Thorup, Optimal evolutionary tree comparison by sparse dynamic programming, IEEE FOCS'94, 1994."},{"key":"13_CR6","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"},{"key":"13_CR7","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979."},{"key":"13_CR8","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/net.3230210104","volume":"21","author":"D. Gusfield","year":"1991","unstructured":"D. Gusfield, Efficient algorithms for inferring evolutionary trees, Networks 21, 19\u201328, 1991.","journal-title":"Networks"},{"key":"13_CR9","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0025-5564(90)90123-G","volume":"98","author":"J. Hein","year":"1990","unstructured":"J. Hein, Reconstructing evolution of sequences subject to recombination using parsimony, Math. Biosci. 98, 185\u2013200, 1990","journal-title":"Math. Biosci."},{"key":"13_CR10","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/BF00182187","volume":"36","author":"J. Hein","year":"1993","unstructured":"J. Hein, A heuristic method to reconstruct the history of sequences subject to recombination, Journal Molecular Evolution 36, 396\u2013405, 1993.","journal-title":"Journal Molecular Evolution"},{"key":"13_CR11","unstructured":"T. Jiang and M. Li, On the approximation of shortest common supersequences and longest common subsequences, to appear in SIAM J. Comput.; also presented at ICALP'94."},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0304-3975(95)80015-8","volume":"143-1","author":"T. Jiang","year":"1995","unstructured":"T. Jiang, L. Wang and K. Zhang, Alignment of trees \u2014 an alternative to tree edit, Theoretical Computer Science 143-1, 137\u2013148, 1995.","journal-title":"Theoretical Computer Science"},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V. Kann","year":"1991","unstructured":"V. Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters 37, 27\u201335, 1991.","journal-title":"Information Processing Letters"},{"key":"13_CR14","unstructured":"J. Kececioglu and D. Gusfield, Reconstructing a history of recombinations from a set of sequences, Proc. 5th ACM-SIAM SODA, 1994."},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"C.H. Papadimitriou and M. Yannakakis, Optimization, Approximation, and complexity classes, Journal of Computer and System Sciences 43, 425\u2013440, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR16","doi-asserted-by":"publisher","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, 77\u201382, 1993.","journal-title":"Information Processing Letters"},{"key":"13_CR17","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1006\/jagm.1994.1018","volume":"16","author":"T. Warnow","year":"1994","unstructured":"T. Warnow, Tree compatibility and inferring evolutionary history, J. of Algorithms 16, 388\u2013407, 1994.","journal-title":"J. of Algorithms"},{"key":"13_CR18","unstructured":"T. Warnow, Private communication, 1994."},{"key":"13_CR19","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/0218082","volume":"18","author":"K. Zhang","year":"1989","unstructured":"K. Zhang and D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM J. Comput. 18, 1245\u20131262, 1989.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60044-2_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T02:21:14Z","timestamp":1578536474000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60044-2_42"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540600442","9783540494126"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-60044-2_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}