Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree
DOI10.1142/S0129054120500069zbMath1458.68137OpenAlexW3011668974WikidataQ115926338 ScholiaQ115926338MaRDI QIDQ5859738
Takeyuki Tamura, Avraham A. Melkman, Tatsuya Akutsu
Publication date: 20 April 2021
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054120500069
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Induced subgraph isomorphism on proper interval and bipartite permutation graphs
- The treewidth of line graphs
- Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees
- Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
- The subgraph isomorphism problem for outerplanar graphs
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- A partial k-arboretum of graphs with bounded treewidth
- Graph searching and a min-max theorem for tree-width
- Enumerating all connected maximal common subgraphs in two graphs
- 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
- Video indexing and similarity retrieval by largest common subgraph detection using decision trees
- Reverse search for enumeration
- A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics
- On the complexity of various parameterizations of common induced subgraph isomorphism
- Maximum common induced subgraph parameterized by vertex cover
- Fixed-Parameter Tractability, Definability, and Model-Checking
- On the Number of Connected Sets in Bounded Degree Graphs
- Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
- The traveling salesman problem in bounded degree graphs
- Computing and Drawing Isomorphic Subgraphs
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms
- Deciding First-Order Properties of Nowhere Dense Graphs
- On the Complexity of the Maximum Common Subgraph Problem for Partial k-Trees of Bounded Degree
- Graph isomorphism in quasipolynomial time [extended abstract]
This page was built for publication: Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree
