Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees
From MaRDI portal
Publication:834895
DOI10.1016/j.ipl.2004.06.019zbMath1173.68533OpenAlexW1999414674WikidataQ57010789 ScholiaQ57010789MaRDI QIDQ834895
Kiyoko F. Aoki, Hiroshi Mamitsuka, Atsuko Yamaguchi
Publication date: 27 August 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2004.06.019
Related Items (8)
On the complexity of various parameterizations of common induced subgraph isomorphism ⋮ Finding Largest Common Substructures of Molecules in Quadratic Time ⋮ Maximum common induced subgraph parameterized by vertex cover ⋮ A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree ⋮ Largest Weight Common Subtree Embeddings with Distance Penalties ⋮ Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree ⋮ Multi-wave tabu search for the Boolean quadratic programming problem with generalized upper bound constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- Video indexing and similarity retrieval by largest common subgraph detection using decision trees
- Complexity of Finding Embeddings in a k-Tree
- Graphs with not too many spanning trees
- On the approximability of the maximum common subgraph problem
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees
