Subgraph isomorphism for biconnected outerplanar graphs in cubic time

DOI10.1016/0304-3975(89)90011-XMaRDI QIDQ1823708zbMATH OpenOpenAlexWikidataFDO

Authors 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

dynamic programming algorithmouterplanar graphssubgraph isomorphism

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3963193
• Subgraph Isomorphism in Planar Graphs and Related Problems
• scientific article; zbMATH DE number 910922
• Efficient Suboptimal Graph Isomorphism
• Planar subgraph isomorphism revisited
• Subexponential parameterized algorithms for bounded-degree connected subgraph problems on planar graphs
• Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees
• Faster algorithms for subgraph isomorphism of k-connected partial k-trees
• scientific article; zbMATH DE number 4072379
• Graph isomorphism in quasipolynomial time (extended abstract)

Cites work

• An Analysis of a Good Algorithm for the Subtree Problem
• scientific article; zbMATH DE number 3949729 (Why is no real title available?)
• scientific article; zbMATH DE number 3679848 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Parallel concepts in graph theory
• Subtree Isomorphism in O(n5/2)
• The subgraph isomorphism problem for outerplanar graphs

Cited in

(21)

• Subtree isomorphism is NC reducible to bipartite perfect matching
• On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
• A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree
• Cleaning interval graphs
• Learning block-preserving graph patterns and its application to data mining
• Maximum packing for biconnected outerplanar graphs
• Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
• Fixed-parameter tractability for the tree assembly problem
• A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics
• Finding largest common substructures of molecules in quadratic time
• scientific article; zbMATH DE number 1542609 (Why is no real title available?)
• A note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs
• Sequential and parallel algorithms for embedding problems on classes of partial k-trees
• The set cover conjecture and subgraph isomorphism with a tree pattern
• Parameterized Graph Cleaning Problems
• Mining of Frequent Block Preserving Outerplanar Graph Structured Patterns
• Subgraph isomorphism on graph classes that exclude a substructure
• The complexity of subgraph isomorphism for classes of partial k-trees
• Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
• Parameterized graph cleaning problems

This page was built for publication: Subgraph isomorphism for biconnected outerplanar graphs in cubic time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1823708)