On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs

DOI10.1016/0304-3975(89)90127-8zbMath0686.68041MaRDI QIDQ1262768

Andrzej Lingas, Andrzej Proskurowski

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)90127-8

zbMATH Keywords

planar graphs; parallel algorithms; subgraph isomorphism; subgraph homeomorphism; NC algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Related Items

Structure and recognition of graphs with no 6-wheel subdivision, Maximum packing for biconnected outerplanar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal parallel algorithms for computing convex hulls and for sorting
• Forbidden minors characterization of partial 3-trees
• The subgraph isomorphism problem for outerplanar graphs
• An approach to the subgraph homeomorphism problem
• Graph minors. V. Excluding a planar graph
• The directed subgraph homeomorphism problem
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• On uniform circuit complexity
• Parallel concepts in graph theory
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• Simulation of Parallel Random Access Machines by Circuits
• Disjoint Paths—A Survey
• Characterization and Recognition of Partial 3-Trees
• An O(logn) parallel connectivity algorithm
• An Analysis of a Good Algorithm for the Subtree Problem
• Correction: Parallel Merge Sort