On the maximum common embedded subtree problem for ordered trees
Valiente Feruglio, Gabriel Alejandro · 2003
The maximum common embedded subtree problem, which generalizes the subtree homeomorphism problem, is reduced for ordered trees to a variant of the longest common subsequence problem, called the longest common balanced sequence problem. While the maximum common embedded subtree problem is known to be APX-hard for unordered trees, an exact solution for ordered trees can be found in polynomial time. A dynamic programming algorithm is presented that solves the longest common balanced sequence problem, and thus the maximum common embedded subtree problem, in (m^2n^2)$ time, where m and n are the number of edges in the trees.