The Largest Common Similar Substructure Problem (Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
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, CO-trees) are proposed. The time complexity of the algorithm for trees is O (max(m_a,m_b)^2N_aN_b) and that for CO-trees is O (m_am_bN_aN_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 CO-trees. The algorithms can be applied to structure-activity studies in chemistry and various structure comparison problems.
社団法人電子情報通信学会の論文
1997-04-25