IEICE TRANSACTIONS on Information
The Distances between Unrooted and Cyclically Ordered Trees and Their Computing Methods
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 (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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E77-D No.10 pp.1094-1105
- Publication Date
- 1994/10/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithm and Computational Complexity
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Shaoming LIU, Eiichi TANAKA, Sumio MASUDA, "The Distances between Unrooted and Cyclically Ordered Trees and Their Computing Methods" in IEICE TRANSACTIONS on Information,
vol. E77-D, no. 10, pp. 1094-1105, October 1994, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e77-d_10_1094/_p
Copy
@ARTICLE{e77-d_10_1094,
author={Shaoming LIU, Eiichi TANAKA, Sumio MASUDA, },
journal={IEICE TRANSACTIONS on Information},
title={The Distances between Unrooted and Cyclically Ordered Trees and Their Computing Methods},
year={1994},
volume={E77-D},
number={10},
pages={1094-1105},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - The Distances between Unrooted and Cyclically Ordered Trees and Their Computing Methods
T2 - IEICE TRANSACTIONS on Information
SP - 1094
EP - 1105
AU - Shaoming LIU
AU - Eiichi TANAKA
AU - Sumio MASUDA
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E77-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 1994
AB - 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.
ER -
English
