The Distances between Unrooted and Cyclically Ordered Trees and Their Computing Methods

Shaoming LIU  Eiichi TANAKA  Sumio MASUDA  

IEICE TRANSACTIONS on Information and Systems   Vol.E77-D   No.10   pp.1094-1105
Publication Date: 1994/10/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
tree,  graph,  distance,  similarity,  algorithm,  pattern matching,  

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

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 (CO-trees) and their computing methods. A CO-tree 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 CO-trees. The time complexities to compute the distances between two CO-trees Ta and Tb are OT (N 2aN 2b) for the distance based on a TM and OT(mambNaNb) for that on an SSPM, respectively, where ma(mb) and Na(Nb) are the largest degree of a vertex and the number of vertices of Ta(Tb), respectively. The space complexities of both methods are Os(NaNb). Those distances can be applied to the clustering of CO-trees.