1+ ε approximation of tree edit distance in quadratic time
Mahdi Boroujeni, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Saeed Seddighin · 2019
Edit distance is one of the most fundamental problems in computer science. Tree edit distance is a natural generalization of edit distance to ordered rooted trees. Such a generalization extends the applications of edit distance to areas such as computational biology, structured data analysis (e.g., XML), image analysis, and compiler optimization. Perhaps the most notable application of tree edit distance is in the analysis of RNA molecules in computational biology where the secondary structure of RNA is typically represented as a rooted tree.