On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
From MaRDI portal
Publication:1262768
DOI10.1016/0304-3975(89)90127-8zbMath0686.68041MaRDI QIDQ1262768
Andrzej Proskurowski, 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)90127-8
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item