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)

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

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)

Cites Work

• Title not available (Why is that?)
• A numbering system for binary trees
• The complexity of drawing trees nicely

Cited In (3)

• Title not available (Why is that?)
• Find subtrees of specified weight and cycles of specified length in linear time
• Optimal binary search trees

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)