IEICE TRANSACTIONS on Fundamentals
Metrics between Trees Embedded in a Plane and Their Computing Methods
Summary :
A tree embedded in a plane can be characterized as an unrooted and cyclically ordered tree (CO-tree). This paper describes new definitions of three distances between CO-trees and their computing methods. The proposed distances are based on the Tai Mapping, the structure preserving mapping and the strongly structure preserving mapping, respectively, and are called the Tai distance (TD), the structure preserving distance (SPD) and the strongly structure preserving distance (SSPD), respectively. The definitions of distances and their computing methods are simpler than those of the old definitions and computing methods, respectively. TD and SPD by the new definitions are more sensitive than those by the old ones, and SSPDs by both definitions are equivalent. The time complexities of computing TD, SPD and SSPD between CO-trees Ta and Tb are OT (N2aN2a), OT(maNaN2b) and OT(mambNaNb), respectively, where Na(Nb) and ma(mb) are the number of vertices in tree Ta(Tb)and the maximum degree of a vertex in Ta(Tb), respectively. The space complexities of these methods are OS(NaNb).
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.4 pp.441-447
- Publication Date
- 1996/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
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
Eiichi TANAKA, "Metrics between Trees Embedded in a Plane and Their Computing Methods" in IEICE TRANSACTIONS on Fundamentals,
vol. E79-A, no. 4, pp. 441-447, April 1996, doi: .
Abstract: A tree embedded in a plane can be characterized as an unrooted and cyclically ordered tree (CO-tree). This paper describes new definitions of three distances between CO-trees and their computing methods. The proposed distances are based on the Tai Mapping, the structure preserving mapping and the strongly structure preserving mapping, respectively, and are called the Tai distance (TD), the structure preserving distance (SPD) and the strongly structure preserving distance (SSPD), respectively. The definitions of distances and their computing methods are simpler than those of the old definitions and computing methods, respectively. TD and SPD by the new definitions are more sensitive than those by the old ones, and SSPDs by both definitions are equivalent. The time complexities of computing TD, SPD and SSPD between CO-trees Ta and Tb are OT (N2aN2a), OT(maNaN2b) and OT(mambNaNb), respectively, where Na(Nb) and ma(mb) are the number of vertices in tree Ta(Tb)and the maximum degree of a vertex in Ta(Tb), respectively. The space complexities of these methods are OS(NaNb).
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e79-a_4_441/_p
Copy
@ARTICLE{e79-a_4_441,
author={Eiichi TANAKA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Metrics between Trees Embedded in a Plane and Their Computing Methods},
year={1996},
volume={E79-A},
number={4},
pages={441-447},
abstract={A tree embedded in a plane can be characterized as an unrooted and cyclically ordered tree (CO-tree). This paper describes new definitions of three distances between CO-trees and their computing methods. The proposed distances are based on the Tai Mapping, the structure preserving mapping and the strongly structure preserving mapping, respectively, and are called the Tai distance (TD), the structure preserving distance (SPD) and the strongly structure preserving distance (SSPD), respectively. The definitions of distances and their computing methods are simpler than those of the old definitions and computing methods, respectively. TD and SPD by the new definitions are more sensitive than those by the old ones, and SSPDs by both definitions are equivalent. The time complexities of computing TD, SPD and SSPD between CO-trees Ta and Tb are OT (N2aN2a), OT(maNaN2b) and OT(mambNaNb), respectively, where Na(Nb) and ma(mb) are the number of vertices in tree Ta(Tb)and the maximum degree of a vertex in Ta(Tb), respectively. The space complexities of these methods are OS(NaNb).},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - Metrics between Trees Embedded in a Plane and Their Computing Methods
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 441
EP - 447
AU - Eiichi TANAKA
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1996
AB - A tree embedded in a plane can be characterized as an unrooted and cyclically ordered tree (CO-tree). This paper describes new definitions of three distances between CO-trees and their computing methods. The proposed distances are based on the Tai Mapping, the structure preserving mapping and the strongly structure preserving mapping, respectively, and are called the Tai distance (TD), the structure preserving distance (SPD) and the strongly structure preserving distance (SSPD), respectively. The definitions of distances and their computing methods are simpler than those of the old definitions and computing methods, respectively. TD and SPD by the new definitions are more sensitive than those by the old ones, and SSPDs by both definitions are equivalent. The time complexities of computing TD, SPD and SSPD between CO-trees Ta and Tb are OT (N2aN2a), OT(maNaN2b) and OT(mambNaNb), respectively, where Na(Nb) and ma(mb) are the number of vertices in tree Ta(Tb)and the maximum degree of a vertex in Ta(Tb), respectively. The space complexities of these methods are OS(NaNb).
ER -
English
