On an algorithm of Zemlyachenko for subtree isomorphism

DOI10.1016/S0020-0190(99)00054-XzbMath1339.05383MaRDI QIDQ294684

Michael Rodeh, Yefim Dinitz, Alon Itai

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

tree; isomorphism; linear time; subtree; trie

Mathematics Subject Classification ID

05C05: Trees

05C85: Graph algorithms (graph-theoretic aspects)

68P05: Data structures

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

FAST ALGORITHMS FOR COMPARISON OF SIMILAR UNORDERED TREES, 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, Exact algorithms for computing the tree edit distance between unordered trees, Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species, An efficient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation, Encoding trees by linear recurrence sequences, Cleaning interval graphs