On the subtree isomorphism problem for ordered trees

DOI10.1016/0020-0190(89)90056-2MaRDI QIDQ1124598zbMATH OpenOpenAlexFDO

Authors Erkki Mäkinen

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90056-2

zbMATH Keywords

isomorphism problemordered tree

Mathematics Subject Classification ID

Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Algorithms in computer science (68W99)

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)\).

Recommendations

• A note on the subtree isomorphism for ordered trees and related problems
• More Efficient Algorithm for Ordered Tree Inclusion
• Some comments on the subtree isomorphism problem for ordered trees
• Strings, trees, and patterns
• Subtree isomorphism revisited

Cites work

• A new algorithm for solving the tree isomorphism problem
• An Analysis of a Good Algorithm for the Subtree Problem
• Fast Pattern Matching in Strings
• Lexicographic generation of ordered trees
• Pattern Matching in Trees

Cited in

(15)

• An efficient algorithm for some tree matching problems
• A note on the subtree isomorphism for ordered trees and related problems
• Further comments on the subtree isomorphism for ordered trees
• Strings, trees, and patterns
• On finding common subtrees
• On the coding of ordered graphs
• Learning grammars for architecture-specific facade parsing
• Constrained tree inclusion
• TOWARDS PARALLEL PROGRAMMING BY TRANSFORMATION: THE FAN SKELETON FRAMEWORK*
• scientific article; zbMATH DE number 3912404 (Why is no real title available?)
• scientific article; zbMATH DE number 1335884 (Why is no real title available?)
• Linear matching-time algorithm for the directed graph isomorphism problem
• Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species
• Some comments on the subtree isomorphism problem for ordered trees
• An efficient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation

This page was built for publication: On the subtree isomorphism problem for ordered trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124598)