On maximum common subgraph problems in series-parallel graphs
From MaRDI portal
Publication:1678090
DOI10.1016/j.ejc.2017.07.012zbMath1373.05120OpenAlexW2963589575WikidataQ115926592 ScholiaQ115926592MaRDI QIDQ1678090
Nils M. Kriege, Florian Kurpicz, Petra Mutzel
Publication date: 14 November 2017
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejc.2017.07.012
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
Unnamed Item, Unnamed Item, Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Effective feature construction by maximum common subgraph sampling
- The complexity of subgraph isomorphism for classes of partial k-trees
- Efficient frequent connected subgraph mining in graphs of bounded tree-width
- The subgraph isomorphism problem for outerplanar graphs
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- A tighter insertion-based approximation of the crossing number
- A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics
- Finding Maximum Common Biconnected Subgraphs in Series-Parallel Graphs
- On Maximum Common Subgraph Problems in Series-Parallel Graphs
- `` Strong NP-Completeness Results
- Subtree Isomorphism in O(n5/2)
- Graph Classes: A Survey
- On the Complexity of the Maximum Common Subgraph Problem for Partial k-Trees of Bounded Degree
- Sequential and parallel algorithms for embedding problems on classes of partial k-trees
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
