Abstract
This paper presents efficient exponential time algorithms for the unordered tree edit distance problem, which is known to be NP-hard. For a general case, an \(O(1.26^{n_1+n_2})\) time algorithm is presented, where n 1 and n 2 are the numbers of nodes in two input trees. This algorithm is obtained by a combination of dynamic programming, exhaustive search, and maximum weighted bipartite matching. For bounded degree trees over a fixed alphabet, it is shown that the problem can be solved in \(O((1+\epsilon)^{n_1+n_2})\) time for any fixed ε > 0. This result is achieved by avoiding duplicate calculations for identical subsets of small subtrees.
This work was partially supported by the Collaborative Research Programs of Institute for Chemical Research, Kyoto University and National Institute of Informatics. T.A. and T.T. were partially supported by JSPS, Japan: Grant-in-Aid 22650045 and Grant-in-Aid 23700017, respectively.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Akutsu, T., Fukagawa, D., Takasu, A., Tamura, T.: Exact algorithms for computing the tree edit distance between unordered trees. Theoret. Comput. Sci. 412, 352–364 (2011)
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–540. IEEE Press, New York (2011)
Akutsu, T., Fukagawa, D., Takasu, A.: Improved approximation of the largest common subtree of two unordered trees of bounded height. Inf. Proc. Lett. 109, 165–170 (2008)
Bille, P.: A survey on tree edit distance and related problem. Theoret. Comput. Sci. 337, 217–239 (2005)
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. 6755, pp. 98–109. Springer, Heidelberg (2011)
Demaine, E.D., Mozes, S., Rossman, B., Weimann, O.: An optimal decomposition algorithm for tree edit distance. ACM Trans. Algorithms 6, 1 (2009)
Fukagawa, D., Akutsu, T., Takasu, A.: Constant Factor Approximation of Edit Distance of Bounded Height Unordered Trees. In: Karlgren, J., Tarhio, J., Hyyrö, H. (eds.) SPIRE 2009. LNCS, vol. 5721, pp. 7–17. Springer, Heidelberg (2009)
Halldórsson, 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. 1178, pp. 75–84. Springer, Heidelberg (1996)
Hirata, K., Yamamoto, Y., Kuboyama, T.: Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 402–415. Springer, Heidelberg (2011)
Kilpeläinen, P., Mannila, H.: Ordered and unordered tree inclusion. SIAM J. Computing 24, 340–356 (1995)
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 24, 668–678 (1994)
Tai, K.-C.: The tree-to-tree correction problem. J. ACM 26, 4220–4433 (1979)
Tovey, C.A.: A simplified satisfiability problem. Disc. Appl. Math. 8, 85–89 (1984)
Zhang, K., Statman, R., Shasha, D.: On the editing distance between unordered labeled trees. Inf. Proc. Lett. 42, 133–139 (1992)
Zhang, K., Jiang, T.: Some MAX SNP-hard results concerning unordered labeled trees. Inf. Proc. Lett. 49, 249–254 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Akutsu, T., Tamura, T., Fukagawa, D., Takasu, A. (2012). Efficient Exponential Time Algorithms for Edit Distance between Unordered Trees. In: Kärkkäinen, J., Stoye, J. (eds) Combinatorial Pattern Matching. CPM 2012. Lecture Notes in Computer Science, vol 7354. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31265-6_29
Download citation
DOI: https://doi.org/10.1007/978-3-642-31265-6_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31264-9
Online ISBN: 978-3-642-31265-6
eBook Packages: Computer ScienceComputer Science (R0)