algoritmo de diferencia eficiente para árboles y distancia de Levenshtein

Recientemente leí este resumen de los problemas relacionados con la diferencia entre los árboles y me interesó aprender cuál es el estado del arte para este problema.

Además, suponga que entre sus operaciones de edición permitidas se encuentran el nodo tradicional de agregar / eliminar, edite el contenido y agregue las operaciones extendidas de copiar / mover subárbol, ¿esto hace que el problema (de encontrar una diferencia óptima) sea más fácil o más difícil?

El siguiente documento describe un algoritmo ligeramente más eficiente que Zhang-Shasha para calcular la distancia de edición del árbol, junto con una prueba de que su algoritmo es óptimo (dentro de una cierta clase amplia de algoritmos):

• Erik Demaine, Shay Mozes, Benjamin Rossman y Oren Weimann. Algoritmo de descomposición óptimo para la distancia de edición de árbol . ACM Transactions on Algorithms , 6 (1), 2009.

Una encuesta útil sobre el tema, un poco desactualizada:

Philip Bille. Una encuesta sobre la distancia de edición del árbol y los problemas relacionados . Ciencias de la computación teóricas, volumen 337, números 1–3, páginas 217–239, 2005.

Un artículo reciente sobre una de las versiones del problema:

Tatsuya Akutsu y col. Algoritmos exactos para calcular la distancia de edición del árbol entre árboles desordenados . Ciencias de la computación teórica, Volumen 412, números 4–5, páginas 352–364, 2011.