Discamus continentiam augere, luxuriam coercere
Home -> Publications
Home
  Publications
    
edited volumes
  Awards
  Research
  Teaching
  BLOG
  Miscellaneous
  Full CV [pdf]
  blog






  Events








  Past Events





Publications of Torsten Hoefler
Lukas Gianinazzi, Torsten Hoefler:

 Parallel Planar Subgraph Isomorphism and Vertex Connectivity

(In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'20), ACM, Jul. 2020)
Best Paper Finalist (5/68)

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 graphs).

Documents

 

BibTeX

@inproceedings{gianinazzi-par-sg-isomorphism,
  author={Lukas Gianinazzi and Torsten Hoefler},
  title={{Parallel Planar Subgraph Isomorphism and Vertex Connectivity}},
  year={2020},
  month={Jul.},
  booktitle={Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'20)},
  publisher={ACM},
  source={http://www.unixer.de/~htor/publications/},
}


serving: 3.238.190.82:36568© Torsten Hoefler