{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T11:40:12Z","timestamp":1737632412418,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540676331"},{"type":"electronic","value":"9783540451235"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45123-4_13","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T19:59:14Z","timestamp":1194983954000},"page":"129-142","source":"Crossref","is-referenced-by-count":0,"title":["A Faster and Unifying Algorithm for Comparing Trees"],"prefix":"10.1007","author":[{"given":"Ming -Yang","family":"Kao","sequence":"first","affiliation":[]},{"given":"Tak -Wah","family":"Lam","sequence":"additional","affiliation":[]},{"given":"Wing -Kin","family":"Sung","sequence":"additional","affiliation":[]},{"given":"Hing -Fung","family":"Ting","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,11,7]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/0196-6774(87)90030-7","volume":"8","author":"M. J. Chung","year":"1987","unstructured":"M. J. Chung. O(n 2.5) time algorithms for the subgraph homeomorphism problem on trees. Journal of Algorithms, 8:106\u2013112, 1987.","journal-title":"Journal of Algorithms"},{"unstructured":"R. Cole and R. Hariharan. An O(n log n) algorithm for the maximum agreement subtree problem for binary trees. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 323\u2013332, 1996.","key":"13_CR2"},{"key":"13_CR3","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1991","unstructured":"T. H. Cormen, C. L. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1991."},{"key":"13_CR4","first-page":"381","volume-title":"Lecture Notes in Computer Science 979: Proceedings of the 3rd Annual European Symposium on Algorithms","author":"M. Farach","year":"1995","unstructured":"M. Farach, T. M. Przytycka, and M. Thorup. Computing the agreement of trees with bounded degrees. In P. Spirakis, editor, Lecture Notes in Computer Science 979: Proceedings of the 3rd Annual European Symposium on Algorithms, pages 381\u2013393. Springer-Verlag, New York, NY, 1995."},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539794262422","volume":"26","author":"M. Farach","year":"1997","unstructured":"M. Farach and M. Thorup. Sparse dynamic programming for evolutionary-tree comparison. SIAM Journal on Computing, 26:210\u2013230, 1997.","journal-title":"SIAM Journal on Computing"},{"key":"13_CR6","doi-asserted-by":"publisher","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:255\u2013276, 1985.","journal-title":"Journal of Classification"},{"key":"13_CR7","first-page":"113","volume-title":"Formal methods in the study of language","author":"J. Friedman","year":"1981","unstructured":"J. Friedman. Expressing logical formulas in natural languages. In J. Groenendijk, T. Janssen, and M. Stokhof, editors, Formal methods in the study of language, pages 113\u2013130. Mathmatical Centre, Amsterdam, 1981."},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"H. N. Gabow","year":"1989","unstructured":"H. N. Gabow and R. E. Tarjan. Faster scaling algorithms for network problems. SIAM Journal on Computing, 18:1013\u20131036, 1989.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"13_CR9","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/PL00009212","volume":"21","author":"A. Gupta","year":"1998","unstructured":"A. Gupta and N. Nishimura. Finding largest subtrees and smallest supertrees. Algorithmica, 21(2): 183\u2013210, 1998.","journal-title":"Algorithmica"},{"key":"13_CR10","volume-title":"Molecular Systematics","year":"1996","unstructured":"D. M. Hillis, C. Moritz, and B. K. Mable, editors. Molecular Systematics. Sinauer Associates, Sunderland, Ma, 2nd edition, 1996.","edition":"2nd edition"},{"key":"13_CR11","doi-asserted-by":"publisher","first-page":"1592","DOI":"10.1137\/S0097539795283504","volume":"27","author":"M. Y. Kao","year":"1998","unstructured":"M. Y. Kao. Tree contractions and evolutionary trees. SIAM Journal on Computing, 27:1592\u20131616, 1998.","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"M. Y. Kao, T. W. Lam, W. K. Sung, and H. F. Ting. All-cavity maximum matchings. In Lecture Notes in Computer Science 1350: Proceedings of the 8th Annual International Symposium on Algorithms and Computation, pages 364\u2013373, 1997.","key":"13_CR12","DOI":"10.1007\/3-540-63890-3_39"},{"key":"13_CR13","first-page":"438","volume-title":"Lecture Notes in Computer Science: Proceedings of the 8th Annual European Symposium on Algorithms","author":"M. Y. Kao","year":"1999","unstructured":"M. Y. Kao, T. W. Lam, W. K. Sung, and H. F. Ting. A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees. In Lecture Notes in Computer Science: Proceedings of the 8th Annual European Symposium on Algorithms, pages 438\u2013449. Springer-Verlag, New York, NY, 1999."},{"doi-asserted-by":"crossref","unstructured":"P. Kilpel\u00e4inen and H. Mannila. Retrieval from hierarchical texts by partial patterns. In Proceedings of the 16th Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval, pages 214\u2013222, 1991.","key":"13_CR14","DOI":"10.1145\/160688.160722"},{"key":"13_CR15","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/3-540-56024-6_13","volume-title":"Lecture Notes in Computer Science 644: Proceedings of the 3rd Annual Symposium on Combinatorial Pattern Matching","author":"P. Kilpel\u00e4inen","year":"1992","unstructured":"P. Kilpel\u00e4inen and H. Mannila. Grammatical tree matching. In A. Apostolico, M. Crochemore, Z. Galil, and U. Manber, editors, Lecture Notes in Computer Science 644: Proceedings of the 3rd Annual Symposium on Combinatorial Pattern Matching, pages 162\u2013174. Springer-Verlag, New York, NY, 1992."},{"doi-asserted-by":"crossref","unstructured":"B. Kimia, A. Tannenbaum, and S. W. Zucker. Shapes, shocks, and deformations, I. International Journal of Computer Vision, pages 189\u2013224, 1995.","key":"13_CR16","DOI":"10.1007\/BF01451741"},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF01202269","volume":"12","author":"E. Kubicka","year":"1995","unstructured":"E. Kubicka, G. Kubicki, and F. McMorris. An algorithm to find agreement subtrees. Journal of Classification, 12:91\u201399, 1995.","journal-title":"Journal of Classification"},{"key":"13_CR18","first-page":"205","volume":"5","author":"S. Y. Le","year":"1989","unstructured":"S. Y. Le, J. Owens, R. Nussinov, J. H. Chen, B. Shapiro, and J. V. Maizel. RNA secondary structures: comparison and determination of frequently recurring substructures by consensus. Computer Application in Bioscience, 5:205\u2013210, 1989.","journal-title":"Computer Application in Bioscience"},{"key":"13_CR19","first-page":"469","volume-title":"Information Modelling and Knowledge Bases","author":"H. Mannila","year":"1990","unstructured":"H. Mannila and K. J. R\u00e4ih\u00e4. On query languages for the p-string data model. In H. Kangassalo, S. Ohsuga, and H. Jaakkola, editors, Information Modelling and Knowledge Bases, pages 469\u2013482. IOS Press, Amsterdam, 1990."},{"unstructured":"P. Materna, P. Sgall, and Z. Hajicova. Linguistic constructions in transparent intensional logic. Prague Bulletin on Mathematical Linguistics, pages 27\u201332, 1985.","key":"13_CR20"},{"doi-asserted-by":"crossref","unstructured":"T. Przytycka. Sparse dynamic programming for maximum agreement subtree problem. In B. Mirkin, F. R. McMorris, F. S. Roberts, and A. Rzhetsky, editors, Mathematical Hierarchies and Biology, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 249\u2013264, Providence, RI, 1997. American Mathematical Society.","key":"13_CR21","DOI":"10.1090\/dimacs\/037\/17"},{"doi-asserted-by":"crossref","unstructured":"B. Shapiro and K. Zhang. Comparing multiple RNA secondary structures using tree comparisons. Compter Applications in Bioscience, pages 309\u2013318, 1990.","key":"13_CR22","DOI":"10.1093\/bioinformatics\/6.4.309"},{"doi-asserted-by":"crossref","unstructured":"F. Y. Shih. Object representation and recognition using mathematical morphology model. Journal of Systems Integration, pages 235\u2013256, 1991.","key":"13_CR23","DOI":"10.1007\/BF02426925"},{"key":"13_CR24","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1109\/34.23111","volume":"11","author":"F. Y. Shih","year":"1989","unstructured":"F. Y. Shih and O. R. Mitchell. Threshold decomposition of grayscale morphology into binary morphology. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11:31\u201342, 1989.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"13_CR25","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"},{"doi-asserted-by":"crossref","unstructured":"Y. Takahashi, Y. Satoh, H. Suzuki, and S. Sasaki. Recognition of largest common structural fragment among a variety of chemical structures. Analytical Science, pages 23\u201328, 1987.","key":"13_CR26","DOI":"10.2116\/analsci.3.23"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45123-4_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T08:16:23Z","timestamp":1737533783000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45123-4_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540676331","9783540451235"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-45123-4_13","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}