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

Bipartite Matching ProblemIsomorphicSubtree IsomorphismTree

Mathematics Subject Classification ID

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

Cited in

(40)

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

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)