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 3a
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Tomokazu MUGURUMA, Eiichi TANAKA, Sumio MASUDA, "A Metric between Unrooted and Unordered Trees and Its Top-down Computing Method" in IEICE TRANSACTIONS on Information,
vol. E77-D, no. 5, pp. 555-566, May 1994, doi: .
Abstract: 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 3a
URL: https://global.ieice.org/en_transactions/information/10.1587/e77-d_5_555/_p
Copy
@ARTICLE{e77-d_5_555,
author={Tomokazu MUGURUMA, Eiichi TANAKA, Sumio MASUDA, },
journal={IEICE TRANSACTIONS on Information},
title={A Metric between Unrooted and Unordered Trees and Its Top-down Computing Method},
year={1994},
volume={E77-D},
number={5},
pages={555-566},
abstract={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 3a
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - A Metric between Unrooted and Unordered Trees and Its Top-down Computing Method
T2 - IEICE TRANSACTIONS on Information
SP - 555
EP - 566
AU - Tomokazu MUGURUMA
AU - Eiichi TANAKA
AU - Sumio MASUDA
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E77-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 1994
AB - 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 3a
ER -