Metrics between Trees Embedded in a Plane and Their Computing Methods

Eiichi TANAKA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.4   pp.441-447
Publication Date: 1996/04/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
distance,  dynamic programming,  pattern matching,  pattern recognition similar structure search,  similarity,  tree,  

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

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).