An Analysis of a Good Algorithm for the Subtree Problem

DOI10.1137/0206053MaRDI QIDQ4142684zbMATH OpenOpenAlexFDO

Authors 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

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

Cited in

(20)

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

This page was built for publication: An Analysis of a Good Algorithm for the Subtree Problem

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