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.
Metrics between Trees Embedded in a Plane and Their Computing Methods
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/04/25
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)>>
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).