Finding the maximum common subgraph of a partial k-tree and a graph with a polynomially bounded number of spanning trees

DOI10.1016/J.IPL.2004.06.019zbMATH Open1173.68533OpenAlexW1999414674WikidataQ57010789 ScholiaQ57010789MaRDI QIDQ834895FDOQ834895

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

Recommendations

• Algorithms and Computation
• On the complexity of the maximum common subgraph problem for partial \(k\)-trees of bounded degree
• On maximum common subgraph problems in series-parallel graphs
• On maximum common subgraph problems in series-parallel graphs
• A polynomial-time algorithm for computing the maximum common subgraph of outerplanar graphs of bounded degree

zbMATH Keywords

computational complexitygraph algorithmsmaximum common subgraph

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Complexity of Finding Embeddings in a k-Tree
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On the approximability of the maximum common subgraph problem
• Video indexing and similarity retrieval by largest common subgraph detection using decision trees
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Title not available (Why is that?)
• Graphs with not too many spanning trees

Cited In (10)

• A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree
• Title not available (Why is that?)
• Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree
• Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
• Largest Weight Common Subtree Embeddings with Distance Penalties
• On the complexity of various parameterizations of common induced subgraph isomorphism
• Maximum common induced subgraph parameterized by vertex cover
• Multi-wave tabu search for the Boolean quadratic programming problem with generalized upper bound constraints
• Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms
• Finding Largest Common Substructures of Molecules in Quadratic Time

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

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