
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Metric between Unrooted and Unordered Trees and Its Topdown Computing Method
Tomokazu MUGURUMA Eiichi TANAKA Sumio MASUDA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E77D
No.5
pp.555566 Publication Date: 1994/05/25
Online ISSN:
DOI:
Print ISSN: 09168532 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: tree metric, tree similarity, unrooted and unordered tree, dynamic programming, chemical information system,
Full Text: PDF(871.6KB)>>
Summary:
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 topdown computing method is proposed using the characteristics of the mapping. The time and space complexities are O_{T}(N ^{2}_{a}N ^{2}_{b}(N ^{3}_{a}N ^{3}_{b})) and O_{s}(N ^{2}_{a}N ^{2}_{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 ^{3}_{a}N ^{3}_{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.

