
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.

The Largest Common Similar Substructure Problem
Shaoming LIU Eiichi TANAKA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E80A
No.4
pp.643650 Publication Date: 1997/04/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: algorithm, complexity, common similar substructure, distance, similarity, tree,
Full Text: PDF(694KB)>>
Summary:
This paper discusses the largest common similar substructure (in short, LCSS) problem for trees. The problem is, for all pairs of "substructure of A and that of B," to find one of them, denoted by A and B', such that A is most similar to B' and the sum of the number of vertices of A and that of B' is largest. An algorithm for the LCSS problem for unrooted and unordered trees (in short, trees) and that for trees embedded in a plane (in short, Cotrees) are proposed. The time complexity of the algorithm for trees is O (max (m_{a}, m_{b})^{2} N_{a}N_{b}) and that for COtrees is O (m_{a}m_{b}N_{a}N_{b}), where, m_{a} (m_{b}) and N_{a} (N_{b}) are the largest degree of a vertex of tree T_{a} (T_{b}) and the number of vertices of T_{a} (T_{b}), respectively. It is easy to modify the algorithms for enumerating all of the LCSSs for trees and COtrees. The algorithms can be applied to structureactivity studies in chemistry and various structure comparison problems.

