O(n2.5) time algorithms for the subgraph homeomorphism problem on trees

DOI10.1016/0196-6774(87)90030-7zbMath0642.68127OpenAlexW2086974119MaRDI QIDQ3783601

Moon Jung Chung

Publication date: 1987

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(87)90030-7

zbMATH Keywords

unrooted treessubtree isomorphism problemsubgraph homeomorphism problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (10)

On generalization/specialization for conceptual graphs ⋮ Probabilistic and exact frequent subtree mining in graphs beyond forests ⋮ A note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs ⋮ Largest Weight Common Subtree Embeddings with Distance Penalties ⋮ On retracts, absolute retracts, and foldings in cographs ⋮ An algebraic view of the relation between largest common subtrees and smallest common supertrees ⋮ Approximate labelled subtree homeomorphism ⋮ Structure and recognition of graphs with no 6-wheel subdivision ⋮ Constrained tree inclusion ⋮ Comparing and distinguishing the structure of biological branching

This page was built for publication: O(n2.5) time algorithms for the subgraph homeomorphism problem on trees