On the subtree isomorphism problem for ordered trees
type: Item
instance of: scholarly article
title: On the subtree isomorphism problem for ordered trees
zbMATH Open document ID: 0679.05024
DOI: 10.1016/0020-0190(89)90056-2
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: An ordered tree \(T_ n\) is a rooted tree with n nodes that has an ordering prescribed for the subtrees incident with each node. The author shows that for any two ordered trees \(T_ m\) and \(T_ n\) there is an algorithm that determines whether \(T_ m\) is isomorphic to any subtree of \(T_ n\) in time \(O(m+n)\).
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 68W99
zbMATH DE Number: 4112612
zbMATH Keywords: isomorphism problem
zbMATH Keywords: ordered tree
author: Erkki Mäkinen
reviewed by: J. W. Moon
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90056-2
OpenAlex ID: W1978139332
cites work: Pattern Matching in Trees
cites work: A new algorithm for solving the tree isomorphism problem
cites work: Fast Pattern Matching in Strings
cites work: An Analysis of a Good Algorithm for the Subtree Problem
cites work: Lexicographic generation of ordered trees
description: scientific article; zbMATH DE number 4112612