Efficient Algorithms for Finding Largest Similar Substructures in Unordered Trees

Shaoming LIU  Eiichi TANAKA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.4   pp.428-440
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)
algorithm,  complexity,  distance,  similar structure,  tree,  

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

This paper discusses the problems of largest similar substructures (in short, LSS) in rooted and unordered trees (in short, R-trees) and those in unrooted and unordered trees (in short, trees). For two R-trees (or trees) Ta and Tb, LSS in Tb to Ta is defined, and two algorithms for finding one of the LSSs for R-trees and that for trees are proposed. The time and space complexities of both algorithms are OT (m3NaNb) and OS(mNaNb), respectively, where m is the largest degree of a vertex of Ta and Tb, and Na(Nb)is the number of vertices of Ta(Tb).