The subgraph isomorphism problem for outerplanar graphs

DOI10.1016/0304-3975(82)90133-5zbMath0522.68061OpenAlexW2172037773MaRDI QIDQ1056237

Maciej M. Sysło

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90133-5

zbMATH Keywords

outerplanar graphsNP-completeplanar graphsubgraph isomorphism problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (21)

Sequential and parallel algorithms for embedding problems on classes of partial k-trees ⋮ Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth ⋮ On the complexity of submap isomorphism and maximum common submap problems ⋮ On maximum common subgraph problems in series-parallel graphs ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Anti-unification in Constraint Logic Programming ⋮ Finding Largest Common Substructures of Molecules in Quadratic Time ⋮ A note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs ⋮ Subgraph isomorphism in graph classes ⋮ Maximum packing for biconnected outerplanar graphs ⋮ Computational complexity of \(k\)-block conjugacy ⋮ Induced subgraph isomorphism on proper interval and bipartite permutation graphs ⋮ A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree ⋮ Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families ⋮ The complexity of subgraph isomorphism for classes of partial k-trees ⋮ A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics ⋮ Efficient frequent connected subgraph mining in graphs of bounded tree-width ⋮ On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs ⋮ Subgraph isomorphism for biconnected outerplanar graphs in cubic time ⋮ Families of nested graphs with compatible symmetric-group actions ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Graphs with forbidden subgraphs
• An Analysis of a Good Algorithm for the Subtree Problem
• Subtree Isomorphism in O(n5/2)

This page was built for publication: The subgraph isomorphism problem for outerplanar graphs