Fast Parallel Algorithms for the Subgraph Homeomorphism & the Subgraph Isomorphism Problems for Classes of Planar Graphs
| dc.contributor.author | Lingas, Andrzej | |
| dc.contributor.author | Proskurowski, Andrzej | |
| dc.date.accessioned | 2023-06-20T19:58:51Z | |
| dc.date.available | 2023-06-20T19:58:51Z | |
| dc.date.issued | 1988-04-06 | |
| dc.description | 23 pages | en_US |
| dc.description.abstract | We consider the problems of subgraph homeomorphism with fixed pattern graph, recognition, and subgraph isomorphism for some classes of planar graphs. Following the results of Robertson and Seymour on forbidden minor characterization, we show that the problems of fixed subgraph homeomorphism and recognition for any family of planar graphs closed under minor taking are in NC (i.e., they can be solved by an algorithm running in poly-log time using polynomial number of processors). We also show that the related subgraph isomorphism problem for biconnected outerplanar ·graphs is in NC. This is the first example of a restriction of subgraph isomorphism to a non-trivial graph family admitting an NC algorithm | en_US |
| dc.identifier.uri | https://hdl.handle.net/1794/28431 | |
| dc.language.iso | en | en_US |
| dc.publisher | University of Oregon | en_US |
| dc.rights | Creative Commons BY-NC-ND 4.0-US | en_US |
| dc.subject | planar graph | en_US |
| dc.subject | input graph | en_US |
| dc.subject | recursive call | en_US |
| dc.subject | simple polygon | en_US |
| dc.subject | subgraph isomorphism | en_US |
| dc.title | Fast Parallel Algorithms for the Subgraph Homeomorphism & the Subgraph Isomorphism Problems for Classes of Planar Graphs | en_US |
| dc.type | Article | en_US |