  Kondo et al. (DS 2014) proposed methods for computing distances between
unordered rooted trees by transforming an instance of the distance computing
problem into an instance of the integer programming problem. They showed that
the tree edit distance, segmental distance, and bottom-up segmental distance
problem can be respectively transformed into an integer program which has
$O(nm)$ variables and $O(n^2m^2)$ constraints, where $n$ and $m$ are the number
of nodes of input trees. In this work, we propose new integer programming
formulations for these three distances and the bottom-up distance by applying
dynamic programming approach. We divide the tree edit distance problem into
$O(nm)$ subproblems each of which has only $O(n + m)$ constraints. For the
other three distances, each subproblem can be reduced to a maximum weighted
matching problem in a bipartite graph which can be solved in polynomial time.
In order to evaluate our methods, we compare our method to the previous one due
to Kondo et al. The experimental results show that the performance of our
methods have been improved remarkably compared to that of the previous method.
