On an algorithm of Zemlyachenko for subtree isomorphism

DOI10.1016/S0020-0190(99)00054-XMaRDI QIDQ294684zbMATH OpenOpenAlexFDO

Authors Alon Itai, Michael Rodeh, Yefim Dinitz

Publication date 16 June 2016

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

Full work available at URL http://www.sciencedirect.com/science/article/pii/S002001909900054X?np=y

zbMATH Keywords

isomorphismlinear timesubtreetreetrie

Mathematics Subject Classification ID

Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Recommendations

• Faster Subtree Isomorphism
• Some comments on the subtree isomorphism problem for ordered trees
• Strings, trees, and patterns
• Subtree isomorphism is in random NC
• A note on the subtree isomorphism for ordered trees and related problems

Cited in

(13)

• Further comments on the subtree isomorphism for ordered trees
• Encoding trees by linear recurrence sequences
• Cleaning interval graphs
• A bisection algorithm for grammar-based compression of ordered trees
• Inferring a graph from path frequency
• The saga of minimum spanning trees
• Efficient enumeration of stereoisomers of tree structured molecules using dynamic programming
• FAST ALGORITHMS FOR COMPARISON OF SIMILAR UNORDERED TREES
• Exact algorithms for computing the tree edit distance between unordered trees
• A linear time and space algorithm for finding isomorphic subtrees of a binary tree
• 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 an algorithm of Zemlyachenko for subtree isomorphism

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