
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.

Metrics between Trees Embedded in a Plane and Their Computing Methods
Eiichi TANAKA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E79A
No.4
pp.441447 Publication Date: 1996/04/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: distance, dynamic programming, pattern matching, pattern recognition similar structure search, similarity, tree,
Full Text: PDF(519.2KB)>>
Summary:
A tree embedded in a plane can be characterized as an unrooted and cyclically ordered tree (COtree). This paper describes new definitions of three distances between COtrees 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 COtrees T_{a} and T_{b} are O_{T} (N^{2}_{a}N^{2}_{a}), O_{T}(m_{a}N_{a}N^{2}_{b}) and O_{T}(m_{a}m_{b}N_{a}N_{b}), respectively, where N_{a}(N_{b}) and m_{a}(m_{b}) are the number of vertices in tree T_{a}(T_{b})and the maximum degree of a vertex in T_{a}(T_{b}), respectively. The space complexities of these methods are O_{S}(N_{a}N_{b}).

