TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE

In this paper, we investigate the problem of computing structural sensitive variations of an unordered tree edit (listance. First, we focus on the variations tractable by the algorithms including the submodule of a network algorithm, either the minimum cost maximum flow algorithm or the maximum weighted bipartite matching algorithm. Then, we show that both network algorithms are replaceable, and hence the time complexity of computing these variations can be reduced to (nrnd) time, where it is the number of nodes in a tree, m is the number of nodes in another tree and d is the in degree of given two trees. Next, we show that the problem of computing the bottom-up distance is MAX SNP-hard. Note that the well linear tune algorithm for the bottom -up distance designed by Valiente (2001) computes just a bottom-up iode (insertion-deletion) distance allowing no substitutions.