A Metric between Unrooted and Unordered Trees and Its Top-down Computing Method

概要

論文の詳細を見る
Many metrics between trees have been proposed. However, there is no research 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 graphs, 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 characteristics of the mapping are investigated. A top-down computing method is proposed using the characteristics of the mapping. The time and space complexities are O_T(N^aN^b(N^a+N^b)) and O_s(N^aN^b), 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^aN^b). The computing time to obtain the distance between a pair of molecular graphs using a computer (SUN SparcStation ELC) is 0.51 seconds on average for all the pairs of 111 molecular graphs that have 12.0 atoms on average. This methic can be applied to the clustering of molecular graphs.
社団法人電子情報通信学会の論文
1994-05-25