Subgraph isomorphism for biconnected outerplanar graphs in cubic time

DOI10.1016/0304-3975(89)90011-XzbMath0681.68090OpenAlexW2071484148WikidataQ127642577 ScholiaQ127642577MaRDI QIDQ1823708

Andrzej Lingas

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90011-x

zbMATH Keywords

outerplanar graphsdynamic programming algorithmsubgraph isomorphism

Mathematics Subject Classification ID

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

Related Items

Sequential and parallel algorithms for embedding problems on classes of partial k-trees ⋮ Parameterized Graph Cleaning Problems ⋮ Subtree isomorphism is NC reducible to bipartite perfect matching ⋮ Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Cleaning interval graphs ⋮ Finding Largest Common Substructures of Molecules in Quadratic Time ⋮ A note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs ⋮ Learning block-preserving graph patterns and its application to data mining ⋮ Maximum packing for biconnected outerplanar graphs ⋮ A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree ⋮ Fixed-parameter tractability for the Tree Assembly problem ⋮ Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time ⋮ 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 ⋮ Parameterized graph cleaning problems ⋮ Unnamed Item ⋮ Mining of Frequent Block Preserving Outerplanar Graph Structured Patterns ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The subgraph isomorphism problem for outerplanar graphs
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Parallel concepts in graph theory
• An Analysis of a Good Algorithm for the Subtree Problem
• Subtree Isomorphism in O(n5/2)