Parallel Planar Subgraph Isomorphism and Vertex Connectivity
METADATA ONLY
Loading...
Author / Producer
Date
2020-07
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
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). © 2020 ACM.
Permanent link
Publication status
published
External links
Editor
Book title
Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures
Journal / series
Volume
Pages / Article No.
269 - 280
Publisher
Association for Computing Machinery
Event
32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020) (virtual)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Graph algorithms; Parallel algorithms; Subgraph isomorphism; Planar graphs; Vertex connectivity; Parameterized complexity
Organisational unit
03950 - Hoefler, Torsten / Hoefler, Torsten
Notes
Due to the Corona virus (COVID-19) the conference was conducted virtually.