论文标题
平行平面子图同构和顶点连接
Parallel Planar Subgraph Isomorphism and Vertex Connectivity
论文作者
论文摘要
我们介绍了第一种平行的固定参数算法，用于平面图，有界形式图以及更一般而言的所有次要局部界限的较小闭合图中的子图同构。我们随机的低深度算法对目标图的大小具有接近线性的工作依赖性。现有的低深度算法不能保证对于任何恒定大小的模式，该作品在渐近上保持不变。通过使用与某些分离循环的连接，我们的子图同构算法可以决定平面图的顶点连接性（具有较高概率）在渐近的接近线性工作和多结合深度中。以前，在平面图中没有知道的次级工作和多同伴深度（尤其是为了区分四连接和五个连接的平面图）。
We present the first parallel fixed-parameter algorithm for subgraph isomorphism in planar graphs, bounded-genus graphs, and, more generally, all minor-closed graphs of locally bounded treewidth. Our randomized low depth algorithm has a near-linear work dependency on the size of the target graph. Existing low depth algorithms do not guarantee that the work remains asymptotically the same for any constant-sized pattern. By using a connection to certain separating cycles, our subgraph isomorphism algorithm can decide the vertex connectivity of a planar graph (with high probability) in asymptotically near-linear work and poly-logarithmic depth. Previously, no sub-quadratic work and poly-logarithmic depth bound was known in planar graphs (in particular for distinguishing between four-connected and five-connected planar graphs).
