2026-08-04T08:45:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17329 2024-03-06T10:59:28Z ddc:004 open_access

On the Complexity of Tree Edit Distance with Variables Akutsu, Tatsuya Mori, Tomoya Nakamura, Naotoshi Kozawa, Satoshi Ueno, Yuhei Sato, Thomas N. Tree edit distance unification parameterized algorithms In this paper, we propose tree edit distance with variables, which is an extension of the tree edit distance to handle trees with variables and has a potential application to measuring the similarity between mathematical formulas. We analyze the computational complexity of several variants of this model. In particular, we show that the problem is NP-complete for ordered trees. We also show for unordered trees that the problem of deciding whether or not the distance is 0 is graph isomorphism complete but can be solved in polynomial time if the maximum outdegree of input trees is bounded by a constant. We also present parameterized and exponential-time algorithms for ordered and unordered cases, respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tatsuya Akutsu and Tomoya Mori and Naotoshi Nakamura and Satoshi Kozawa and Yuhei Ueno and Thomas N. Sato 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.44 urn:nbn:de:0030-drops-173295 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.44 eng https://creativecommons.org/licenses/by/4.0/legalcode