{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T06:48:57Z","timestamp":1772520537375,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642312649","type":"print"},{"value":"9783642312656","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31265-6_29","type":"book-chapter","created":{"date-parts":[[2012,6,12]],"date-time":"2012-06-12T03:28:23Z","timestamp":1339471703000},"page":"360-372","source":"Crossref","is-referenced-by-count":5,"title":["Efficient Exponential Time Algorithms for Edit Distance between Unordered Trees"],"prefix":"10.1007","author":[{"given":"Tatsuya","family":"Akutsu","sequence":"first","affiliation":[]},{"given":"Takeyuki","family":"Tamura","sequence":"additional","affiliation":[]},{"given":"Daiji","family":"Fukagawa","sequence":"additional","affiliation":[]},{"given":"Atsuhiro","family":"Takasu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1016\/j.tcs.2010.10.002","volume":"412","author":"T. Akutsu","year":"2011","unstructured":"Akutsu, T., Fukagawa, D., Takasu, A., Tamura, T.: Exact algorithms for computing the tree edit distance between unordered trees. Theoret. Comput. Sci.\u00a0412, 352\u2013364 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"29_CR2","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1109\/CISIS.2011.88","volume-title":"Proc. 5th International Conference on Complex, Intelligent and Software Intensive System","author":"T. Akutsu","year":"2011","unstructured":"Akutsu, T., Mori, T., Tamura, T., Fukagawa, D., Takasu, A., Tomita, E.: An improved clique-based method for computing edit distance between unordered trees and its application to comparison of glycan structures. In: Proc. 5th International Conference on Complex, Intelligent and Software Intensive System, pp. 536\u2013540. IEEE Press, New York (2011)"},{"key":"29_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 subtree of two unordered trees of bounded height. Inf. Proc. Lett.\u00a0109, 165\u2013170 (2008)","journal-title":"Inf. Proc. Lett."},{"key":"29_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 problem. Theoret. Comput. Sci.\u00a0337, 217\u2013239 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"29_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-642-22006-7_9","volume-title":"Automata, Languages and Programming","author":"S. Canzar","year":"2011","unstructured":"Canzar, S., Elbassioni, K., Klau, G.W., Mestre, J.: On Tree-Constrained Matchings and Generalizations. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol.\u00a06755, pp. 98\u2013109. Springer, Heidelberg (2011)"},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1644015.1644017","volume":"6","author":"E.D. Demaine","year":"2009","unstructured":"Demaine, E.D., Mozes, S., Rossman, B., Weimann, O.: An optimal decomposition algorithm for tree edit distance. ACM Trans. Algorithms\u00a06, 1 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"29_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/978-3-642-03784-9_2","volume-title":"String Processing and Information Retrieval","author":"D. Fukagawa","year":"2009","unstructured":"Fukagawa, D., Akutsu, T., Takasu, A.: Constant Factor Approximation of Edit Distance of Bounded Height Unordered Trees. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 7\u201317. Springer, Heidelberg (2009)"},{"key":"29_CR8","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":"29_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/978-3-642-21458-5_34","volume-title":"Combinatorial Pattern Matching","author":"K. Hirata","year":"2011","unstructured":"Hirata, K., Yamamoto, Y., Kuboyama, T.: Improved MAX\u00a0SNP-Hard Results for Finding an Edit Distance between Unordered Trees. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 402\u2013415. Springer, Heidelberg (2011)"},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1137\/S0097539791218202","volume":"24","author":"P. Kilpel\u00e4inen","year":"1995","unstructured":"Kilpel\u00e4inen, P., Mannila, H.: Ordered and unordered tree inclusion. SIAM J. Computing\u00a024, 340\u2013356 (1995)","journal-title":"SIAM J. Computing"},{"key":"29_CR11","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1109\/21.286387","volume":"24","author":"D. Shasha","year":"1994","unstructured":"Shasha, D., Wang, J.T.-L., Zhang, K., Shih, F.Y.: Exact and approximate algorithms for unordered tree matching. IEEE Trans. System, Man, and Cybernetics\u00a024, 668\u2013678 (1994)","journal-title":"IEEE Trans. System, Man, and Cybernetics"},{"key":"29_CR12","doi-asserted-by":"publisher","first-page":"4220","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, 4220\u20134433 (1979)","journal-title":"J. ACM"},{"key":"29_CR13","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"C.A. Tovey","year":"1984","unstructured":"Tovey, C.A.: A simplified satisfiability problem. Disc. Appl. Math.\u00a08, 85\u201389 (1984)","journal-title":"Disc. Appl. Math."},{"key":"29_CR14","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(92)90136-J","volume":"42","author":"K. Zhang","year":"1992","unstructured":"Zhang, K., Statman, R., Shasha, D.: On the editing distance between unordered labeled trees. Inf. Proc. Lett.\u00a042, 133\u2013139 (1992)","journal-title":"Inf. Proc. Lett."},{"key":"29_CR15","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."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31265-6_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:54:15Z","timestamp":1620129255000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31265-6_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642312649","9783642312656"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31265-6_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}