{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:49:51Z","timestamp":1725490191954},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540412557"},{"type":"electronic","value":"9783540409960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-40996-3_41","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T21:17:32Z","timestamp":1188335852000},"page":"479-490","source":"Crossref","is-referenced-by-count":0,"title":["Unbalanced and Hierarchical Bipartite Matchings with Applications to Labeled Tree Comparison"],"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,1,29]]},"reference":[{"issue":"5","key":"41_CR1","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1137\/S0097539791199334","volume":"23","author":"R. K. Ahuja","year":"1994","unstructured":"R. K. Ahuja, J. B. Orlin, C. Stein, and R. E. Tarjan. Improved algorithms for bipartite network flow. SIAM Journal on Computing, 23(5):906\u2013933, 1994.","journal-title":"SIAM Journal on Computing"},{"key":"41_CR2","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"},{"key":"41_CR3","unstructured":"R. Cole, M. Farach, R. Hariharan, T. M. Przytycka, and M. Thorup. An O(n log n) time algorithm for the maximum agreement subtree problem for binary trees. SIAM Journal on Computing. To appear."},{"key":"41_CR4","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":"41_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/3-540-60313-1_157","volume-title":"Computing the agreement of trees with bounded degrees","author":"M. Farach","year":"1995","unstructured":"M. Farach, T. M. Przytycka, and M. Thorup. Computing the agreement of trees with bounded degrees. In Lecture Notes in Computer Science 979: Proceedings of the 3rd Annual European Symposium on Algorithms, pages 381\u2013393. 1995."},{"issue":"1","key":"41_CR6","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(1):210\u2013230, 1997.","journal-title":"SIAM Journal on Computing"},{"key":"41_CR7","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":"41_CR8","unstructured":"J. Friedman. Expressing logical formulas in natural languages. In Formal methods in the study of language, pages 113\u2013130. Mathematical Centre, Amsterdam, 1981."},{"issue":"5","key":"41_CR9","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(5):1013\u20131036, 1989.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"41_CR10","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":"41_CR11","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1137\/0216020","volume":"16","author":"D. Gusfield","year":"1987","unstructured":"D. Gusfield, C. Martel, and D. Fern\u00e1ndez-Baca. Fast algorithms for bipartite network flow. SIAM Journal on Computing, 16:237\u2013251, 1987.","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"41_CR12","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(6):1592\u20131616, 1998.","journal-title":"SIAM Journal on Computing"},{"key":"41_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1007\/3-540-48481-7_38","volume-title":"A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees","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. 1999."},{"key":"41_CR14","first-page":"129","volume-title":"Combinatorial Pattern Matching","author":"Ming -Yang Kao","year":"2000","unstructured":"M. Y. Kao, T. W. Lam, W. K. Sung, and H. F. Ting. A faster and unifying algorithm for comparing trees. In Proceedings of the 11th Symposium on Combinatorial Pattern matching, 2000. To appear."},{"key":"41_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/3-540-56024-6_13","volume-title":"Grammatical tree matching","author":"P. Kilpel\u00e4inen","year":"1992","unstructured":"P. Kilpel\u00e4inen and H. Mannila. Grammatical tree matching. In Lecture Notes in Computer Science 644: Proceedings of the 3rd Annual Symposium on Combinatorial Pattern Matching, pages 162\u2013174. 1992."},{"key":"41_CR16","unstructured":"H. Mannila and K. J. R\u00e4ih\u00e4. On query languages for the p-string data model. In Information Modelling and Knowledge Bases, pages 469\u2013482. 1990."},{"key":"41_CR17","unstructured":"P. Materna, P. Sgall, and Z. Hajicova. Linguistic constructions in transparent intensional logic. Prague Bulletin on Mathematical Linguistics, pages 27\u201332, 1985."},{"key":"41_CR18","doi-asserted-by":"crossref","unstructured":"T. Przytycka. Sparse dynamic programming for maximum agreement subtree problem. In Mathematical Hierarchies and Biology, pages 249\u2013264, 1997.","DOI":"10.1090\/dimacs\/037\/17"},{"issue":"4","key":"41_CR19","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1093\/bioinformatics\/6.4.309","volume":"6","author":"Bruce A. Shapiro","year":"1990","unstructured":"B. Shapiro and K. Zhang. Comparing multiple RNA secondary structures using tree comparisons. Computer Applications in Bioscience, pages 309\u2013318, 1990.","journal-title":"Bioinformatics"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-40996-3_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T13:26:11Z","timestamp":1556803571000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-40996-3_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540412557","9783540409960"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-40996-3_41","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}