DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2022.44

On the Complexity of Tree Edit Distance with Variables

Authors: Tatsuya Akutsu, Tomoya Mori, Naotoshi Nakamura, Satoshi Kozawa, Yuhei Ueno, and Thomas N. Sato

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

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.

Cite as

Tatsuya Akutsu, Tomoya Mori, Naotoshi Nakamura, Satoshi Kozawa, Yuhei Ueno, and Thomas N. Sato. On the Complexity of Tree Edit Distance with Variables. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ISAAC.2022.44},
  URN =		{urn:nbn:de:0030-drops-173295},
  doi =		{10.4230/LIPIcs.ISAAC.2022.44},
  annote =	{Keywords: Tree edit distance, unification, parameterized algorithms}
}

Search Results

Documents authored by Nakamura, Naotoshi

On the Complexity of Tree Edit Distance with Variables

Abstract

Cite as

Thanks for your feedback!

Could not send message