ON THE SUBTREE ISOMORPHISM-PROBLEM FOR ORDERED TREES

作     者：MAKINEN, E 

作者机构：University of Tampere Department of Computer Science P.O. Box 607 SF-33101 Tampere Finland 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：1989年第32卷第5期

页      面：271-273页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Ordered tree tree isomorphism Zasks sequence string pattern matching 

摘      要：In the subtree isomorphism problem, given 2 rooted trees T subscript 1 and T subscript 2, a determination is made as to whether T subscript 1 is isomorphic to any subtree of T subscript 2. A tree is considered ordered if the relative order of its subtrees in each node is fixed. It is shown that a O(m+n) time algorithm can be obtained when dealing only with ordered trees. The algorithm is based on tree encoding and on string pattern matching. The subtree isomorphism problem has connections with the tree pattern matching problem, in which nodes are labeled and the trees may contain special symbols that stand for arbitrary trees. While several algorithms already exist to reduce the tree pattern matching problem to string matching, algorithms with a time complexity of less than O(mn) are obtained only in some special cases.