Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)

Bringmann, K; Gawrychowski, P; Mozes, S; Weimann, O

Bringmann, K (corresponding author), Max Planck Inst Informat, Saarland Informat Campus, Saarbrucken, Germany.

ACM TRANSACTIONS ON ALGORITHMS, 2020; 16 (4):

Abstract

The edit distance between two rooted ordered trees with n nodes labeled from an alphabet Sigma is the minimum cost of transforming one tree into the o......

Full Text Link