For Full-Text 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
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1994/10/25
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)>>
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.