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

DOI10.1016/0304-3975(89)90127-8zbMath0686.68041OpenAlexW2019615222MaRDI 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 graphsparallel algorithmssubgraph isomorphismsubgraph homeomorphismNC algorithm

Mathematics Subject Classification ID

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

Related Items (2)

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

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

This page was built for publication: On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs