Subtree Isomorphism in O(n5/2)

DOI10.1016/S0167-5060(08)70324-8zbMath0391.05022OpenAlexW108777047MaRDI QIDQ4172071

David W. Matula

Publication date: 1978

Published in: Algorithmic Aspects of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-5060(08)70324-8

zbMATH Keywords

TreeBipartite Matching ProblemIsomorphicSubtree Isomorphism

Mathematics Subject Classification ID

Trees (05C05) Graph theory (05C99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (33)

Sequential and parallel algorithms for embedding problems on classes of partial k-trees ⋮ Parameterized Graph Cleaning Problems ⋮ Isomorphic tree spanner problems ⋮ Subtree isomorphism is NC reducible to bipartite perfect matching ⋮ Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth ⋮ On the complexity of submap isomorphism and maximum common submap problems ⋮ On maximum common subgraph problems in series-parallel graphs ⋮ The parallel complexity of tree embedding problems (extended abstract) ⋮ Maximum tree-packing in time \(O(n^{5/2})\) ⋮ Maximum tree-packing in time O(n5/2) ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Polynomial time algorithms for variants of graph matching on partial \(k\)-trees ⋮ Cleaning interval graphs ⋮ A note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs ⋮ Maximum packing for biconnected outerplanar graphs ⋮ Subtree isomorphism is in random NC ⋮ Induced subgraph isomorphism on proper interval and bipartite permutation graphs ⋮ Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time ⋮ Largest Weight Common Subtree Embeddings with Distance Penalties ⋮ Graph Similarity and Approximate Isomorphism ⋮ The complexity of subgraph isomorphism for classes of partial k-trees ⋮ Parameterized graph cleaning problems ⋮ Efficient frequent connected subgraph mining in graphs of bounded tree-width ⋮ Unnamed Item ⋮ Computational aspects of mining maximal frequent patterns ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ Finding a Forest in a Tree ⋮ Approximate labelled subtree homeomorphism ⋮ FAST ALGORITHMS FOR COMPARISON OF SIMILAR UNORDERED TREES ⋮ Subgraph isomorphism for biconnected outerplanar graphs in cubic time ⋮ Constrained tree inclusion ⋮ The subgraph isomorphism problem for outerplanar graphs ⋮ Concerning the achromatic number of graphs

This page was built for publication: Subtree Isomorphism in O(n5/2)