{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:43:48Z","timestamp":1750693428859},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319684734"},{"type":"electronic","value":"9783319684741"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-68474-1_11","type":"book-chapter","created":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T15:15:48Z","timestamp":1506525348000},"page":"156-170","source":"Crossref","is-referenced-by-count":15,"title":["A New Perspective on the Tree Edit Distance"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Schwarz","sequence":"first","affiliation":[]},{"given":"Mateusz","family":"Pawlik","sequence":"additional","affiliation":[]},{"given":"Nikolaus","family":"Augsten","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,9,28]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Augsten, N., B\u00f6hlen, M., Gamper, J.: The pq-gram distance between ordered labeled trees. ACM Trans. Database Syst. (TODS) 35(1) (2010)","key":"11_CR1","DOI":"10.1145\/1670243.1670247"},{"doi-asserted-by":"crossref","unstructured":"Bringmann, K., Gawrychowski, P., Mozes, S., Weimann, O.: Tree edit distance cannot be computed in strongly subcubic time (unless APSP can). CoRR, abs\/1703.08940 (2017)","key":"11_CR2","DOI":"10.1137\/1.9781611975031.77"},{"doi-asserted-by":"crossref","unstructured":"Bringmann, K., Grandoni, F., Saha, B., Williams, V.V.: Truly sub-cubic algorithms for language edit distance and RNA-folding via fast bounded-difference min-plus product. In: IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 375\u2013384 (2016)","key":"11_CR3","DOI":"10.1109\/FOCS.2016.48"},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1007\/11816102_54","volume-title":"Computational Intelligence and Bioinformatics","author":"TYT Chan","year":"2006","unstructured":"Chan, T.Y.T.: Practical linear space algorithms for computing string-edit distances. In: Huang, D.-S., Li, K., Irwin, G.W. (eds.) ICIC 2006. LNCS, vol. 4115, pp. 504\u2013513. Springer, Heidelberg (2006). doi: 10.1007\/11816102_54"},{"doi-asserted-by":"crossref","unstructured":"Chen, S., Zhang, K.: An improved algorithm for tree edit distance incorporating structural linearity. In: International Conference on Computing and Combinatorics (COCOON) (2007)","key":"11_CR5","DOI":"10.1007\/978-3-540-73545-8_47"},{"issue":"2","key":"11_CR6","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1006\/jagm.2001.1170","volume":"40","author":"W Chen","year":"2001","unstructured":"Chen, W.: New algorithm for ordered tree-to-tree correction problem. J. Algorithms 40(2), 135\u2013158 (2001)","journal-title":"J. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Mozes, S., Rossman, B., Weimann, O.: An optimal decomposition algorithm for tree edit distance. ACM Trans. Algorithms 6(1) (2009)","key":"11_CR7","DOI":"10.1145\/1644015.1644017"},{"issue":"2\u20134","key":"11_CR8","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/j.jda.2004.08.018","volume":"3","author":"S Dulucq","year":"2005","unstructured":"Dulucq, S., Touzet, H.: Decomposition algorithms for the tree edit distance problem. J. Discrete Algorithms 3(2\u20134), 448\u2013471 (2005)","journal-title":"J. Discrete Algorithms"},{"key":"11_CR9","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/j.tcs.2015.09.008","volume":"609","author":"KCK Fong","year":"2016","unstructured":"Fong, K.C.K., Li, M., Liang, H., Yang, L., Yuan, H.: Average-case complexity of the min-sum matrix product problem. Theoret. Comput. Sci. 609, 76\u201386 (2016)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"11_CR10","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"ML Fredman","year":"1976","unstructured":"Fredman, M.L.: New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5(1), 83\u201389 (1976)","journal-title":"SIAM J. Comput."},{"key":"11_CR11","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 \u2014 ESA\u2019 98","author":"PN Klein","year":"1998","unstructured":"Klein, P.N.: Computing the edit-distance between unrooted ordered trees. In: Bilardi, G., Italiano, G.F., Pietracaprina, A., Pucci, G. (eds.) ESA 1998. LNCS, vol. 1461, pp. 91\u2013102. Springer, Heidelberg (1998). doi: 10.1007\/3-540-68530-8_8"},{"issue":"4","key":"11_CR12","doi-asserted-by":"crossref","first-page":"334","DOI":"10.14778\/2095686.2095692","volume":"5","author":"M Pawlik","year":"2011","unstructured":"Pawlik, M., Augsten, N.: RTED: a robust algorithm for the tree edit distance. Proc. VLDB Endow. (PVLDB) 5(4), 334\u2013345 (2011)","journal-title":"Proc. VLDB Endow. (PVLDB)"},{"doi-asserted-by":"crossref","unstructured":"Pawlik, M., Augsten, N.: Efficient computation of the tree edit distance. ACM Trans. Database Syst. (TODS) 40(1) (2015). Article No. 3","key":"11_CR13","DOI":"10.1145\/2699485"},{"key":"11_CR14","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/j.is.2015.08.004","volume":"56","author":"M Pawlik","year":"2016","unstructured":"Pawlik, M., Augsten, N.: Tree edit distance: robust and memory-efficient. Inf. Syst. 56, 157\u2013173 (2016)","journal-title":"Inf. Syst."},{"issue":"3","key":"11_CR15","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"11_CR16","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/322139.322143","volume":"26","author":"H-C Tai","year":"1979","unstructured":"Tai, H.-C.: The tree-to-tree correction problem. J. ACM (JACM) 26(3), 422\u2013433 (1979)","journal-title":"J. ACM (JACM)"},{"issue":"3","key":"11_CR17","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/s00453-007-9100-z","volume":"51","author":"L Wang","year":"2008","unstructured":"Wang, L., Zhang, K.: Space efficient algorithms for ordered tree comparison. Algorithmica 51(3), 283\u2013297 (2008)","journal-title":"Algorithmica"},{"issue":"6","key":"11_CR18","doi-asserted-by":"crossref","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. Comput. 18(6), 1245\u20131262 (1989)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"11_CR19","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1145\/567112.567114","volume":"49","author":"U Zwick","year":"2002","unstructured":"Zwick, U.: All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM (JACM) 49(3), 289\u2013317 (2002)","journal-title":"J. ACM (JACM)"}],"container-title":["Lecture Notes in Computer Science","Similarity Search and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-68474-1_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T01:15:51Z","timestamp":1570151751000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-68474-1_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319684734","9783319684741"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-68474-1_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}