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.019MaRDI QIDQ834895zbMATH OpenOpenAlexWikidataFDO

Authors Atsuko Yamaguchi, Kiyoko F. Aoki, Hiroshi Mamitsuka

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

zbMATH Keywords

computational complexitygraph algorithmsmaximum common subgraph

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 47903 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Complexity of Finding Embeddings in a k-Tree
• Graphs with not too many spanning trees
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On the approximability of the maximum common subgraph problem
• 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

Cited in

(12)

• scientific article; zbMATH DE number 1864596 (Why is no real title available?)
• Largest Weight Common Subtree Embeddings with Distance Penalties
• On maximum common subgraph problems in series-parallel graphs
• On the complexity of the maximum common subgraph problem for partial \(k\)-trees of bounded degree
• Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
• Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms
• Maximum common induced subgraph parameterized by vertex cover
• Improved hardness of maximum common subgraph problems on labeled graphs of bounded treewidth and bounded degree
• Finding largest common substructures of molecules in quadratic time
• A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree
• Finding maximum common biconnected subgraphs in series-parallel graphs
• Multi-wave tabu search for the Boolean quadratic programming problem with generalized upper bound constraints

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)