A METRIC BETWEEN UNROOTED AND UNORDERED TREES AND ITS TOP-DOWN COMPUTING METHOD

Many metrics between trees have been proposed. However, there is no re search on a graph metric that can be applied to molecular graphs. And most of the reports on tree metrics have dealt with rooted and ordered trees. As the first step to defining a graph metric for molecular gra phs, this paper proposes a tree metric between unrooted and unordered trees. This metric is based on a mapping between trees that determines a transformation from one tree to another. The metric is the minimum weight among the weights of all possible transformations. The characte ristics of the mapping are investigated. A top-down computing method i s proposed using the characteristics of the mapping. The time and spac e complexities are O(T)(N(a)2N(b)2(N(a)3+N(b)3)) and O(S)(N(a)2N(b)2), respectively, where N(a) and N(b) are the numbers of vertices of the two trees. If the degrees of all vertices of the trees are bounded by a constant, the time complexity of the method is O(N(a)3N(b)3). The co mputing time to obtain the distance between a pair of molecular graphs using a computer (SUN SparcStation ELC) is 0.51 seconds on average fo r all the pairs of 111 molecular graphs that have 12.0 atoms on averag e. This methic can be applied to the clustering of molecular graphs.