A linear time and space algorithm for finding isomorphic subtrees of a binary tree

DOI10.1007/BF01931294zbMATH Open0726.68045MaRDI QIDQ802874FDOQ802874

Authors Erkki Mäkinen

Publication date 1991

Published in BIT (Search for Journal in Brave)

zbMATH Keywords

binary treeisomorphic subtrees

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Recommendations

• A BULT algorithm for tree isomorphism
• scientific article; zbMATH DE number 3959487
• Faster Subtree Isomorphism
• A linear time algorithm for finding an optimal degree-bounded subtree of an edge-weighted tree
• An optimal algorithm for computing all subtree repeats in trees
• An optimal algorithm for computing all subtree repeats in trees
• The Space Complexity of k-Tree Isomorphism
• On an algorithm of Zemlyachenko for subtree isomorphism
• Faster algorithms for the maximum common subtree isomorphism problem
• Tree Pattern Matching to Subset Matching in Linear Time

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• A numbering system for binary trees
• The complexity of drawing trees nicely

Cited in

(3)

• Optimal binary search trees
• scientific article; zbMATH DE number 3885345 (Why is no real title available?)
• Find subtrees of specified weight and cycles of specified length in linear time

This page was built for publication: A linear time and space algorithm for finding isomorphic subtrees of a binary tree

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