{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:44:15Z","timestamp":1725536655414},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642037832"},{"type":"electronic","value":"9783642037849"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03784-9_2","type":"book-chapter","created":{"date-parts":[[2009,8,21]],"date-time":"2009-08-21T14:47:42Z","timestamp":1250866062000},"page":"7-17","source":"Crossref","is-referenced-by-count":2,"title":["Constant Factor Approximation of Edit Distance of Bounded Height Unordered Trees"],"prefix":"10.1007","author":[{"given":"Daiji","family":"Fukagawa","sequence":"first","affiliation":[]},{"given":"Tatsuya","family":"Akutsu","sequence":"additional","affiliation":[]},{"given":"Atsuhiro","family":"Takasu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston (1974)"},{"key":"2_CR2","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.ipl.2006.06.002","volume":"100","author":"T. Akutsu","year":"2006","unstructured":"Akutsu, T.: A relation between edit distance for ordered trees and edit distance for euler strings. Inf. Proc. Lett.\u00a0100, 105\u2013109 (2006)","journal-title":"Inf. Proc. Lett."},{"key":"2_CR3","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.ipl.2008.09.025","volume":"109","author":"T. Akutsu","year":"2008","unstructured":"Akutsu, T., Fukagawa, D., Takasu, A.: Improved approximation of the largest common sub-tree of two unordered trees of bounded height. Inf. Proc. Lett.\u00a0109, 165\u2013170 (2008)","journal-title":"Inf. Proc. Lett."},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.tcs.2004.12.030","volume":"337","author":"P. Bille","year":"2005","unstructured":"Bille, P.: A survey on tree edit distance and related problems. Theor. Comput. Sci.\u00a0337, 217\u2013239 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Collins, M., Duffy, N.: Convolution Kernels for Natural Language. In: Proc. NIPS, pp. 625\u2013632 (2001)","DOI":"10.7551\/mitpress\/1120.003.0085"},{"key":"2_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/978-3-540-73420-8_15","volume-title":"Automata, Languages and Programming","author":"E.D. Demaine","year":"2007","unstructured":"Demaine, E.D., Mozes, S., Rossman, B., Weimann, O.: An optimal decomposition algorithm for tree edit distance. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 146\u2013157. Springer, Heidelberg (2007)"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1145\/1061318.1061326","volume":"30","author":"M.N. Garofalakis","year":"2005","unstructured":"Garofalakis, M.N., Kumar, A.: XML stream processing using tree-edit distance embeddings. ACM Trans. Database System\u00a030, 279\u2013332 (2005)","journal-title":"ACM Trans. Database System"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Guha, S., Jagadish, H.V., Koudas, N., Srivastava, D., Yu, T.: Approximate XML joins. In: SIGMOD 2002 (2002)","DOI":"10.1145\/564691.564725"},{"key":"2_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BFb0009483","volume-title":"Algorithms and Computation","author":"M.M. Halld\u00f3rsson","year":"1996","unstructured":"Halld\u00f3rsson, M.M., Tanaka, K.: Approximation and special cases of common subtrees and editing distance. In: Nagamochi, H., Suri, S., Igarashi, Y., Miyano, S., Asano, T. (eds.) ISAAC 1996. LNCS, vol.\u00a01178, pp. 75\u201384. Springer, Heidelberg (1996)"},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development\u00a031, 249\u2013260 (1987)","journal-title":"IBM Journal of Research and Development"},{"key":"2_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/3-540-68530-8_8","volume-title":"Algorithms - ESA \u201998","author":"P.N. Klein","year":"1998","unstructured":"Klein, P.N.: Computing the edit-distance between unrooted ordered trees. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 91\u2013102. Springer, Heidelberg (1998)"},{"key":"2_CR12","series-title":"Fascicle 4: Generating All Trees","volume-title":"The Art of Computer Programming","author":"D.E. Knuth","year":"2006","unstructured":"Knuth, D.E.: The Art of Computer Programming. Fascicle 4: Generating All Trees, vol.\u00a04. Addison-Wesley Professional, Reading (2006)"},{"key":"2_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)"},{"key":"2_CR14","unstructured":"M\u00fcller-Molina, A.J., Hirata, K., Shinohara, T.: A tree distance function based on multi-sets. In: ALSIP 2008, PAKDD Workshops, pp. 90\u2013100 (2008)"},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/322139.322143","volume":"26","author":"K.-C. Tai","year":"1979","unstructured":"Tai, K.-C.: The tree-to-tree correction problem. J. ACM\u00a026, 422\u2013433 (1979)","journal-title":"J. ACM"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Valiente, G.: An Efficient Bottom-Up Distance between Trees. In: Proc. Eighth Int\u2019l Symp. String Processing Information Retrieval, pp. 212\u2013219 (2001)","DOI":"10.1109\/SPIRE.2001.989761"},{"key":"2_CR17","unstructured":"Vishwanathan, S.V.N., Smola, A.J.: Fast Kernels for String and Tree Matching. In: NIPS, pp. 569\u2013576 (2002)"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Yang, R., Kalnis, P., Tung, A.K.H.: Similarity evaluation on tree-structured data. In: SIGMOD (2005)","DOI":"10.1145\/1066157.1066243"},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF01975866","volume":"15","author":"K. Zhang","year":"1996","unstructured":"Zhang, K.: A constrained edit distance between unordered labeled trees. Algorithmica\u00a015, 205\u2013222 (1996)","journal-title":"Algorithmica"},{"key":"2_CR20","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0020-0190(94)90062-0","volume":"49","author":"K. Zhang","year":"1994","unstructured":"Zhang, K., Jiang, T.: Some MAX SNP-hard results concerning unordered labeled trees. Inf. Proc. Lett.\u00a049, 249\u2013254 (1994)","journal-title":"Inf. Proc. Lett."},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/0218082","volume":"18","author":"K. Zhang","year":"1989","unstructured":"Zhang, K., Shasha, D.: Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Computing\u00a018, 1245\u20131262 (1989)","journal-title":"SIAM J. Computing"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03784-9_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,16]],"date-time":"2024-03-16T00:24:43Z","timestamp":1710548683000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03784-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642037832","9783642037849"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03784-9_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}