{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T03:21:58Z","timestamp":1761708118939},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540734192"},{"type":"electronic","value":"9783540734208"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73420-8_15","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T14:58:43Z","timestamp":1188053923000},"page":"146-157","source":"Crossref","is-referenced-by-count":39,"title":["An Optimal Decomposition Algorithm for Tree Edit Distance"],"prefix":"10.1007","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[]},{"given":"Shay","family":"Mozes","sequence":"additional","affiliation":[]},{"given":"Benjamin","family":"Rossman","sequence":"additional","affiliation":[]},{"given":"Oren","family":"Weimann","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"volume-title":"Pattern matching algorithms","year":"1997","key":"15_CR1","unstructured":"Apostolico, A., Galil, Z. (eds.): Pattern matching algorithms. Oxford University Press, Oxford, UK (1997)"},{"key":"15_CR2","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. Theoretical computer science\u00a0337, 217\u2013239 (2005)","journal-title":"Theoretical computer science"},{"key":"15_CR3","unstructured":"Chawathe, S.S.: Comparing hierarchical data in external memory. In: Proceedings of the 25th International Conference on Very Large Data Bases, pp. 90\u2013101. Edinburgh, Scotland, U.K (1999)"},{"key":"15_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/3-540-44888-8_7","volume-title":"Combinatorial Pattern Matching","author":"S. Dulucq","year":"2003","unstructured":"Dulucq, S., Touzet, H.: Analysis of tree edit distance algorithms. In: Baeza-Yates, R.A., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol.\u00a02676, pp. 83\u201395. Springer, Heidelberg (2003)"},{"key":"15_CR5","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees and sequences: computer science and computational biology","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on strings, trees and sequences: computer science and computational biology. Cambridge University Press, Cambridge (1997)"},{"issue":"2","key":"15_CR6","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM Journal of Computing\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM Journal of Computing"},{"key":"15_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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":"15_CR8","first-page":"696","volume-title":"SODA","author":"P.N. Klein","year":"2000","unstructured":"Klein, P.N., Tirthapura, S., Sharvit, D., Kimia, B.B.: A tree-edit-distance algorithm for comparing simple, closed shapes. In: SODA. Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 696\u2013704. ACM Press, New York (2000)"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1146\/annurev.biochem.68.1.287","volume":"68","author":"P.B. Moore","year":"1999","unstructured":"Moore, P.B.: Structural motifs in RNA. Annual review of biochemistry\u00a068, 287\u2013300 (1999)","journal-title":"Annual review of biochemistry"},{"issue":"6","key":"15_CR10","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/0020-0190(77)90064-3","volume":"6","author":"S.M. Selkow","year":"1977","unstructured":"Selkow, S.M.: The tree-to-tree editing problem. Information Processing Letters\u00a06(6), 184\u2013186 (1977)","journal-title":"Information Processing Letters"},{"issue":"6","key":"15_CR11","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/0218082","volume":"18","author":"D. Shasha","year":"1989","unstructured":"Shasha, D., Zhang, K.: Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal of Computing\u00a018(6), 1245\u20131262 (1989)","journal-title":"SIAM Journal of Computing"},{"issue":"4","key":"15_CR12","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1016\/0196-6774(90)90011-3","volume":"11","author":"D. Shasha","year":"1990","unstructured":"Shasha, D., Zhang, K.: Fast algorithms for the unit cost editing distance between trees. Journal of Algorithms\u00a011(4), 581\u2013621 (1990)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"15_CR13","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/322139.322143","volume":"26","author":"K. Tai","year":"1979","unstructured":"Tai, K.: The tree-to-tree correction problem. Journal of the Association for Computing Machinery (JACM)\u00a026(3), 422\u2013433 (1979)","journal-title":"Journal of the Association for Computing Machinery (JACM)"},{"key":"15_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04921-1","volume-title":"Algorithms on Trees and Graphs","author":"G. Valiente","year":"2002","unstructured":"Valiente, G.: Algorithms on Trees and Graphs. Springer, Heidelberg (2002)"},{"issue":"1","key":"15_CR15","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R.A. Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. Journal of the ACM\u00a021(1), 168\u2013173 (1974)","journal-title":"Journal of the ACM"},{"key":"15_CR16","unstructured":"Waterman, M.S.: Introduction to computational biology: maps, sequences and genomes. chapters 13,14 Chapman and Hall (1995)"},{"issue":"3","key":"15_CR17","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1016\/0031-3203(94)00109-Y","volume":"28","author":"K. Zhang","year":"1995","unstructured":"Zhang, K.: Algorithms for the constrained editing distance between ordered labeled trees and related problems. Pattern Recognition\u00a028(3), 463\u2013474 (1995)","journal-title":"Pattern Recognition"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73420-8_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:10:58Z","timestamp":1619518258000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734192","9783540734208"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}