On the complexity of the maximum common subgraph problem for partial k-trees of bounded degree

DOI10.1007/978-3-642-35261-4_18MaRDI QIDQ4909531zbMATH OpenOpenAlexFDO

Authors Tatsuya Akutsu, Takeyuki Tamura

Publication date 21 March 2013

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-35261-4_18

zbMATH Keywords

maximum common subgraphNP-hardpartial \(k\)-treetreewidth

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Improved hardness of maximum common subgraph problems on labeled graphs of bounded treewidth and bounded degree
• Algorithms and Computation
• On maximum common subgraph problems in series-parallel graphs
• On maximum common subgraph problems in series-parallel graphs
• Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees

Cited in

(17)

• On the complexity of submap isomorphism and maximum common submap problems
• On maximum common subgraph problems in series-parallel graphs
• A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree
• The maximum common edge subgraph problem: A polyhedral investigation
• Maximum common induced subgraph parameterized by vertex cover
• A polynomial-time algorithm for computing the maximum common subgraph of outerplanar graphs of bounded degree
• Finding maximum common biconnected subgraphs in series-parallel graphs
• Enumeration of Maximum Common Subtree Isomorphisms with Polynomial-Delay
• On maximum common subgraph problems in series-parallel graphs
• scientific article; zbMATH DE number 1472113 (Why is no real title available?)
• On the approximability of the maximum common subgraph problem
• A simple linear-time algorithm for computing the centroid and canonical form of a plane graph and its applications
• Improved hardness of maximum common subgraph problems on labeled graphs of bounded treewidth and bounded degree
• Formulations for the maximum common edge subgraph problem
• Maximum common induced subforests and minimum common induced superforests of a set of forests
• Largest common subgraph of two forests
• Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees

This page was built for publication: On the complexity of the maximum common subgraph problem for partial \(k\)-trees of bounded degree

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