On the Complexity of Tree Edit Distance with Variables
On the Complexity of Tree Edit Distance with Variables
复制标题
DOI：
10.4230/lipics.isaac.2022.44
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
T. Akutsu;Tomoya Mori;Naotoshi Nakamura;Satoshi Kozawa;Yuhei Ueno;Thomas N. Sato
中科院分区：
文献类型：
--
作者：
T. Akutsu;Tomoya Mori;Naotoshi Nakamura;Satoshi Kozawa;Yuhei Ueno;Thomas N. Sato
在本文中，我们提出了树编辑距离与变量，这是一个扩展的树编辑距离处理树与变量，并有一个潜在的应用，以衡量数学公式之间的相似性。我们分析了这个模型的几个变种的计算复杂性。特别是，我们证明了这个问题是NP-完全的有序树。我们还表明，无序树的问题，决定是否是0的距离是图同构完成，但可以在多项式时间内解决，如果输入树的最大出度是由一个常数。我们还提出了参数化和指数时间算法的有序和无序的情况下，分别
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