On the Complexity of the Maximum Common Subgraph Problem for Partial k-Trees of Bounded Degree

DOI10.1007/978-3-642-35261-4_18zbMath1260.68169OpenAlexW202023760MaRDI QIDQ4909531

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

treewidthNP-hardpartial \(k\)-treemaximum common subgraph

Mathematics Subject Classification ID

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

Related Items (5)

On maximum common subgraph problems in series-parallel graphs ⋮ 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 ⋮ Unnamed Item ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree

This page was built for publication: On the Complexity of the Maximum Common Subgraph Problem for Partial k-Trees of Bounded Degree