Subtree Isomorphism in O(n5/2)

DOI10.1016/S0167-5060(08)70324-8MaRDI QIDQ4172071zbMATH OpenOpenAlexFDO

Authors 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)

Cited in

(36)

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

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

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