
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.

The Distances between Unrooted and Cyclically Ordered Trees and Their Computing Methods
Shaoming LIU Eiichi TANAKA Sumio MASUDA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E77D
No.10
pp.10941105 Publication Date: 1994/10/25
Online ISSN:
DOI:
Print ISSN: 09168532 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: tree, graph, distance, similarity, algorithm, pattern matching,
Full Text: PDF>>
Summary:
Several distances between trees have been proposed. However, most of the reports on distances have dealt with rooted and ordered trees. This paper proposes two distances between unrooted and cyclically ordered trees (COtrees) and their computing methods. A COtree is a tree embedded in a plane. These distances are defined based on Tai's mapping (TM) and a strongly structure preserving mapping (SSPM) between COtrees. The time complexities to compute the distances between two COtrees T_{a} and T_{b} are O_{T} (N ^{2}_{a}N ^{2}_{b}) for the distance based on a TM and O_{T}(m_{a}m_{b}N_{a}N_{b}) for that on an SSPM, respectively, where m_{a}(m_{b}) and N_{a}(N_{b}) are the largest degree of a vertex and the number of vertices of T_{a}(T_{b}), respectively. The space complexities of both methods are O_{s}(N_{a}N_{b}). Those distances can be applied to the clustering of COtrees.

