An Analysis of a Good Algorithm for the Subtree Problem

DOI10.1137/0206053zbMath0366.68026OpenAlexW2020556510MaRDI QIDQ4142684

Steven W. Reyner

Publication date: 1977

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0206053

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Algorithms in computer science (68W99)

Related Items

Isomorphic tree spanner problems ⋮ Subtree isomorphism is NC reducible to bipartite perfect matching ⋮ On the subtree isomorphism problem for ordered trees ⋮ Some complexity theoretic aspects of AC rewriting ⋮ On generalization/specialization for conceptual graphs ⋮ Maximum tree-packing in time \(O(n^{5/2})\) ⋮ Maximum tree-packing in time O(n5/2) ⋮ A note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs ⋮ Some comments on the subtree isomorphism problem for ordered trees ⋮ On retracts, absolute retracts, and foldings in cographs ⋮ Tight complexity bounds for term matching problems ⋮ Retrieving articulated 3-D models using medial surfaces ⋮ On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs ⋮ Approximate labelled subtree homeomorphism ⋮ Subgraph isomorphism for biconnected outerplanar graphs in cubic time ⋮ On the approximation of largest common subtrees and largest common point sets ⋮ Constrained tree inclusion ⋮ The subgraph isomorphism problem for outerplanar graphs ⋮ Relational object recognition from large structural libraries