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

Tomokazu MUGURUMA  Eiichi TANAKA  Sumio MASUDA  

IEICE TRANSACTIONS on Information and Systems   Vol.E77-D   No.5   pp.555-566
Publication Date: 1994/05/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
tree metric,  tree similarity,  unrooted and unordered tree,  dynamic programming,  chemical information system,  

Full Text: PDF(871.6KB)
>>Buy this Article

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 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 OT(N 2aN 2b(N 3aN 3b)) and Os(N 2aN 2b), respectively, where Na and Nb 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 3aN 3b). 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.