Subtree Isomorphism in O(n5/2)
From MaRDI portal
Publication:4172071
DOI10.1016/S0167-5060(08)70324-8zbMATH Open0391.05022OpenAlexW108777047MaRDI QIDQ4172071FDOQ4172071
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
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
- Dichotomies for tree minor containment with structural parameters
- Subgraph isomorphism for biconnected outerplanar graphs in cubic time
- 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
- FAST ALGORITHMS FOR COMPARISON OF SIMILAR UNORDERED TREES
- Isomorphic tree spanner problems
- The complexity of subgraph isomorphism for classes of partial k-trees
- Parameterized Graph Cleaning Problems
- Title not available (Why is that?)
- 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)
