Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.44
URN: urn:nbn:de:0030-drops-173295
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17329/
Akutsu, Tatsuya ; Mori, Tomoya ; Nakamura, Naotoshi ; Kozawa, Satoshi ; Ueno, Yuhei ; Sato, Thomas N.
On the Complexity of Tree Edit Distance with Variables
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{akutsu_et_al:LIPIcs.ISAAC.2022.44,
author = {Akutsu, Tatsuya and Mori, Tomoya and Nakamura, Naotoshi and Kozawa, Satoshi and Ueno, Yuhei and Sato, Thomas N.},
title = {{On the Complexity of Tree Edit Distance with Variables}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {44:1--44:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17329},
URN = {urn:nbn:de:0030-drops-173295},
doi = {10.4230/LIPIcs.ISAAC.2022.44},
annote = {Keywords: Tree edit distance, unification, parameterized algorithms}
}
| Keywords: | Tree edit distance, unification, parameterized algorithms | |
| Seminar: | 33rd International Symposium on Algorithms and Computation (ISAAC 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 14.12.2022 |
